Problem description:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

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]”
Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution:

The idea is to use preorder traversal to generate the string and create the tree.

  1. serialize
    Use stringstream to build the string.
    Traverse the Tree with preorder traversal
    Insert empty node as ‘#’, separate the nodes between ‘ ‘.

  2. deserialize
    Since we use preorder to store the tree, use preorder to deserialize it.
    idea is to use a queue to store all the nodes in data. The istringstream is already a queue and can help to separate string

Store the tree as a string, use , to separate each node. Use # to mark it as empty node.

When deserialize, use a global variable to process the data. Because the right side of tree would pick up the rest after left side is processed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
example:
-----
1,2,#,#,3,4,#,#,5,#,#
-----
2,#,#,3,4,#,#,5,#,#
-----
#,#,3,4,#,#,5,#,#
-----
#,3,4,#,#,5,#,#
-----
3,4,#,#,5,#,#
-----
4,#,#,5,#,#
-----
#,#,5,#,#
-----
#,5,#,#
-----
5,#,#
-----
#,#
-----
#
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root):
        if not root:
            return "#"
        return ','.join([str(root.val), self.serialize(root.left), self.serialize(root.right)])
        

    def deserialize(self, data):
        self.data = data
        # print("-----")
        # print(self.data)
        if self.data[0] == "#":
            return None
        
        node = TreeNode(self.data[:self.data.find(",")])
        node.left = self.deserialize(self.data[self.data.find(",")+1:])
        node.right = self.deserialize(self.data[self.data.find(",")+1:])
        return node
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
/**
 * 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:
    
    //searialize
    //Use stringstream to build the string. Traverse the Tree with preorder traversal. insert empty node as '#', separate the nodes between ' '
    
    //deserialize
    //idea is to use a queue to store all the nodes in data. The istringstream is already a queue and can help to separate string
    //still use preorder traversal
    string serialize(TreeNode* root) {
        ostringstream out;
        serialize(root, out);
        return out.str();
    }

    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserialize(in);
    }

private:

    void serialize(TreeNode* root, ostringstream& out) {
        if (root) {
            out << root->val << ' ';
            serialize(root->left, out);
            serialize(root->right, out);
        } else {
            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;
    }
    
};


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

time complexity: O(n)

reference:
https://goo.gl/xoE4oD
https://goo.gl/Gn3Uc2

Solution 2 BFS:

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:
    def serialize(self, root):
        if not root:
            return ""
        queue = deque([root])
        res = []
        while queue:
            front = queue.popleft()
            if front:
                queue.append(front.left)
                queue.append(front.right)
            res.append(str(front.val) if front else "#")
        return ','.join(res)

    def deserialize(self, data):
        if not data:
            return None
        nodes = data.split(',')
        root = TreeNode(int(nodes[0]))
        queue = deque([root])
        index = 1
        while queue:
            front = queue.popleft()
            if nodes[index] != '#':
                front.left = TreeNode(int(nodes[index]))
                queue.append(front.left)
            index += 1
            
            if nodes[index] != '#':
                front.right = TreeNode(int(nodes[index]))
                queue.append(front.right)
            index += 1
        return root
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
/**
 * 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 res;
        queue<TreeNode*> q;
        q.push(root);
        res+= to_string(root->val)+ " ";
        
        while(!q.empty()){
            TreeNode* tmp= q.front(); q.pop();
            if(!tmp) res+= "# ";
            else{
                if(tmp->left == NULL)
                    res+= "# ";
                else{
                    q.push(tmp->left);
                    res+= to_string(tmp->left->val)+ " ";
                }
                if(tmp->right == NULL)
                    res+= "# ";
                else{
                    q.push(tmp->right);
                    res+= to_string(tmp->right->val)+ " ";
                }
            }
        }
        cout<< res<<endl;
        return res;
    }
    
    

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data[0] == '#') return NULL;
        vector<string> tokens= helper(data, ' ');
        int i= 0;
        TreeNode *root= new TreeNode(stoi(tokens[i++]));
        queue<TreeNode*> q;
        q.push(root);
        
        while(!q.empty()){
            queue<TreeNode*> newQ;
            while(!q.empty()){
                TreeNode *tmp= q.front(); q.pop();
                //printf("queue front= %d\n", tmp->val);
                if(tokens[i] == "#")
                    tmp->left= NULL;
                else{
                    tmp->left= new TreeNode(stoi(tokens[i]));
                    newQ.push(tmp->left);
                }
                i++;

                if(tokens[i] == "#")
                    tmp->right= NULL;
                else{
                    tmp->right= new TreeNode(stoi(tokens[i]));
                    newQ.push(tmp->right);
                }
                i++;
            }
            q= newQ;
            //printf("q size= %d\n", q.size());
        }
        return root;
    }
    
    vector<string> helper(string &data, char delimiter){
        vector<string> tokens;
        string token;
        istringstream iss(data);
        while(getline(iss, token, delimiter)){
            tokens.push_back(token);
        }
        
        //for(auto s: tokens)
        //    cout<<s<<endl;
        return tokens;
    }
    
};

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