leetcode 297. Serialize and deserialize binary tree

Posted on |

For example, you may serialize the following tree

1
2
3
4
5
   1
 / \
2   3
   / \
  4   5

as "[1,2,3,null,null,4,5]".

这道题看似简单，写起来真是费劲。。。要注意如下几点：

  1. 如何处理int -> string。如果每个节点的值都是个位数的话，那么只需要root->val + '0'即可转化为字符。代码写起来也相对简单。但是考虑节点值有可能不止一位，我们必须采用其他方法。最先想到的是使用to_string()方法，应该可以实现我们想要的结果。后来看到网友写的使用ostringstream。感觉很巧妙，并且代码和前者一样简介，决定采用这种方法。
  2. 如何serialize。第一想法是按层遍历，但是这样会很难处理nullptr：如果事先不知道二叉树的层数，循环就无法跳出。因此，我们使用前序遍历来序列化整个二叉树，这样解码的时候也可以通过同样的顺序建树。
  3. 如何deserialize。如前面所说，不能简单利用队列按层构建二叉树，而要用前序遍历。同时，因为我们保存的字符串使用空格分隔，最快速的方法就是istringstream解析整数值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// leetcode 297. Serialize and Deserialize Binary Tree
// HARD
/**
 * 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) {
        ostringstream os;
        serialize(root, os);
        return os.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        cout << "len: " << data.size() << endl << "data: " << data << endl;
        istringstream is(data);
        return deserialize(is);
    }

private:
    void serialize(TreeNode* root, ostringstream& os) {
        if(root){
            os << root->val << " ";
            serialize(root->left, os);
            serialize(root->right, os);
        }
        else {
            os << "# ";
        }
        return;
    }

    TreeNode* deserialize(istringstream& is){
        string x;
        is >> x;
        if(x == "#"){
            return nullptr;
        }
        TreeNode* new_node = new TreeNode(stoi(x));
        new_node->left = deserialize(is);
        new_node->right = deserialize(is);
        return new_node;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));