Algorithm

LintCode/Binary Tree Serialization

Problem Summary

Serialize and deserialize a binary tree, i.e., write the tree to a string and read the string to reconstruct the exact same binary tree.

Solution

There are many ways to ‘serialize’ the tree that we can choose from, such as:

  1. The BFS traversal of the tree.
  2. The preorder and inorder traversal of the tree.

I chose the frist one.

Code

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode * root) {
        string s;
        queue<TreeNode *> q;
        if (root)
            q.push(root);
        else
            return "";
        while (!q.empty())
        {
            TreeNode *cur = q.front();
            q.pop();
            if (cur == NULL)
            {
                s += "#";
                continue;
            }
            s += to_string(cur->val) + ",";
            q.push(cur->left);
            q.push(cur->right);
        }
        return s;
    }
    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode * deserialize(string &data) {
        if (data.length() == 0)
            return NULL;
        TreeNode * root = new TreeNode(0);
        int i = 0;
        while (data[i] != ',')
            root->val = 10 * root->val + data[i++] - '0';
        ++i;
        vector<TreeNode *> pre,now;
        pre.push_back(root);
        while (i < data.length())
        {
            for (int j = 0; j < pre.size(); ++j)
            {
                TreeNode *cur = pre[j];
                i = get_val(data,i,&cur->left,now);
                i = get_val(data,i,&cur->right,now);
            }
            pre = now;
            now = vector<TreeNode *>();
        }
        return root;
    }
    int get_val(string &data,int i,TreeNode **p,vector<TreeNode *> &now)
    {
        if (data[i] == '#')
        {
            *p = NULL;
            return i+1;
        }
        int tmp = 0;
        while (data[i] != ',')
            tmp = 10 * tmp + data[i++] - '0';
        
        *p = new TreeNode(tmp);
        now.push_back(*p);
        return i+1;
    }
};