序列化二叉树(剑指Offer-37)

题面

请实现两个函数，分别用来序列化和反序列化二叉树。

示例

1你可以将以下二叉树：
2
3    1
4   / \
5  2   3
6     / \
7    4   5
8
9序列化为 "[1,2,3,null,null,4,5]"

思路

BFS层序遍历即可，注意，如果节点为null，则它的子节点就不记录。

即

1     1
2      \
3       2
4      /
5     3

表示为[1,null,2,3] 而非[1,null,2,null,null,3]

反序列化时不能使用父子节点的下标关系。

代码

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Codec {
11public:
12
13    // Encodes a tree to a single string.
14    string serialize(TreeNode* root) {
15        if(root == nullptr) return "[]";
16        string res = "[";
17        queue<TreeNode *> q;
18        q.push(root);
19        while(!q.empty()){
20            TreeNode *t = q.front(); q.pop();
21            if(t == nullptr){
22                res += "null,";
23            }else{
24                res += to_string(t->val) + ",";
25                q.push(t->left);
26                q.push(t->right);
27            }
28        }
29        res[res.length()-1] = ']';
30        return res;
31    }
32
33    // Decodes your encoded data to tree.
34    TreeNode* deserialize(string data) {
35        if(data=="[]") return nullptr;
36        vector<TreeNode *> v;
37        for(int i=0; i<data.length(); i++){
38            if(data[i]=='-' || isdigit(data[i])){
39                int f=1, x=0;
40                if(data[i]=='-'){
41                    f = -1;
42                    i++;
43                }
44                for(; isdigit(data[i]); i++){
45                    x = x*10 + (data[i]-'0');
46                }
47                i--; x *= f;
48                TreeNode *p = new TreeNode(x);
49                v.push_back(p);
50            }else if(data[i]=='n'){
51                v.push_back(nullptr);
52                i += 3;
53            }
54        }
55        for(int i=0, j=1; i<v.size()&&j<v.size(); i++,j++){
56            while(v[i]==nullptr) i++;
57            v[i]->left = v[j++];
58            v[i]->right = v[j];
59        }
60        return v[0];
61    }
62};
63
64// Your Codec object will be instantiated and called as such:
65// Codec codec;
66// codec.deserialize(codec.serialize(root));