树的序列化与反序列化

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

树的序列化就是把树转化成字符串存储，反序列化就是把树从字符串转回树形

序列化的过程就是，先把根结点存入队列，（若不为空）则把其转成字符串存入字符流中（其实就是拼接字符串），再把它的左右子树加入到队列，作为根节点继续递归构造。如果结点为空，则在字符串拼接”#”作为标记。最后返回字符串流转成的字符串即可。
反序列化的过程和序列化相反，但也是借助队列，通过层序遍历构造树。读入字符串的每一个字符，判断是否为“#”(为空结点)，若不是，则加入队列作为根节点继续构造。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return string();
        stringstream ss;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            auto t = q.front(); 
            q.pop();
            if (!t) ss << "# ";
            else
            {
                ss << to_string(t -> val) << " " ;
                q.push(t -> left);
                q.push(t -> right);
            }
        }
        return ss.str();
    }

    // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;
        stringstream ss(data);//将字符串data复制到ss中
        string t;
        ss >> t;//相当于把ss的每个字符一个个输入t中
        queue<TreeNode*> q;
        auto root = new TreeNode(stoi(t));
        q.push(root);
        while (q.size())
        {
            auto p = q.front(); 
            q.pop();
            //创建左子树
            ss >> t;　//读入字符串中除空格的每个字符
            if (t == "#") p ->left = NULL;
            else
            {
                p -> left = new TreeNode(stoi(t));
                q.push(p -> left);
            }
            //创建右子树
            ss >> t;
            if (t == "#") p -> right = NULL;
            else{
                p -> right = new TreeNode(stoi(t));
                q.push(p -> right);
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

FEATURED TAGS

FRIENDS