297. Serialize and Deserialize Binary Tree.md

297. Serialize and Deserialize Binary Tree

思路

对二叉树进行序列化和去序列化的操作。

思路一

本质上就是遍历二叉树，那我们考虑用递归前序遍历二叉树。

• 序列化：

  • 如果节点为空则添加"# "（用空格作为分隔符，这样就可以用字符串流）；
  • 否则添加节点值（要紧跟一个空格）再递归进入左右孩子。

• 去序列化：

  • 如果当前字符为"#"，则返回空；
  • 否则根据字符串的值新建节点，然后递归求其左右孩子。

我们可以用输入/输出字符串流istringstream/ostringstream来进行处理，详见代码。

思路二

我们还可以用非递归的层序遍历，这样就类似LeetCode使用的方法了。

• 序列化：

  • 将根节点入队列，循环直到队列为空：出队首元素，若其为空则添加"# "；否则添加节点值（要紧跟一个空格），另外还要将其左右孩子入队（即使孩子为空）。

• 去序列化：

  • 先处理得到根节点，然后将根节点入队，循环直到队列空：处理得到队首节点的左孩子，即将队首元素的左指针指向当前处理得到的节点，若这个左孩子不为空还要将其入队；再用类似的方法处理得到队首节点的右孩子；最后将队首元素出队。

同样用输入/输出字符串流istringstream/ostringstream来进行处理，详见代码。

本质都是遍历二叉树，所以两个思路时空复杂度均为O(n)

C++

思路一

class Codec {
private:
    void serialize(TreeNode* root, ostringstream &out){
        if(!root) out << "# ";
        else{
            out << root -> val << " ";
            serialize(root -> left, out);
            serialize(root -> right, out);
        }
    }
    TreeNode* deserialize(istringstream &in){
        string val;
        in >> val;
        if(val == "#") return NULL;
        
        TreeNode *root = new TreeNode(stoi(val));
        root -> left = deserialize(in);
        root -> right = deserialize(in);
        return root;
    }
        
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "";
        ostringstream out;
        serialize(root, out);
        return out.str();   
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(!data.size()) return NULL;
        
        istringstream in(data);
        return deserialize(in);
    }
};

思路二

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "";
        ostringstream out;
        
        TreeNode *p;
        queue<TreeNode *>q;
        q.push(root);
        
        while(!q.empty()){
            p = q.front(); q.pop();
            if(!p) out << "# ";
            else{
                out << p -> val << " ";
                q.push(p -> left);
                q.push(p -> right);
            }
        }
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int len = data.size();
        if(!len) return NULL;
        
        queue<TreeNode *>q;
        TreeNode *p = NULL, *root = NULL;
        
        istringstream in(data);
        string val;
        
        // 根节点
        in >> val;
        p = new TreeNode(stoi(val)); root = p;
        q.push(p);
        
        while(!q.empty()){
            in >> val; // 左孩子
            if(val != "#"){
                p = new TreeNode(stoi(val)); 
                q.push(p);
                q.front() -> left = p;
            }
            
            in >> val; // 右孩子
            if(val != "#"){
                p = new TreeNode(stoi(val)); 
                q.push(p);
                q.front() -> right = p;
            }
            q.pop();
        }
        return root;
    }
};