297. Serialize and Deserialize Binary Tree

  • 32.4%

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.

1
2
3
4
5
6
7
For example, you may serialize the following tree

1
/ \
2 3
/ \
4 5

as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ 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.


剑指offer 62 题

https://discuss.leetcode.com/topic/28041/recursive-preorder-python-and-c-o-n

Recursive preorder, Python and C++, O(n)

Python

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
class Codec:

def serialize(self, root):
def doit(node):
if node:
vals.append(str(node.val))
doit(node.left)
doit(node.right)
else:
vals.append('#')
vals = []
doit(root)
return ' '.join(vals)

def deserialize(self, data):
def doit():
val = next(vals)
if val == '#':
return None
node = TreeNode(int(val))
node.left = doit()
node.right = doit()
return node
vals = iter(data.split())
return doit()

C++

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
class Codec {
public:

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 nullptr;
TreeNode* root = new TreeNode(stoi(val));
root->left = deserialize(in);
root->right = deserialize(in);
return root;
}
};

https://discuss.leetcode.com/topic/32470/clean-c-solution

Clean C++ solution

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
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == nullptr) return "#";
return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right);
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return mydeserialize(data);
}
TreeNode* mydeserialize(string& data) {
if (data[0]=='#') {
if(data.size() > 1) data = data.substr(2);
return nullptr;
} else {
TreeNode* node = new TreeNode(helper(data));
node->left = mydeserialize(data);
node->right = mydeserialize(data);
return node;
}
}
private:
int helper(string& data) {
int pos = data.find(',');
int val = stoi(data.substr(0,pos));
data = data.substr(pos+1);
return val;
}
};

https://discuss.leetcode.com/topic/28011/c-accepted-o-n-easy-solution

C++ Accepted O(n) Easy Solution

Idea: Level-order traversal. Use ‘#’ to denote a nullptr. User ‘,’ to separate entries. The output is very similar to Leetcode’s default deserialization logic.

Time Complexities: O(n) to serialize and O(n) to deserialize

Space Complexities: O(n) to serialize and O(n) to deserialize

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:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
string str;
while (!q.empty()) {
if (q.front() == nullptr) {
str = str + "#,";
} else {
q.push(q.front()->left);
q.push(q.front()->right);
str = str + to_string(q.front()->val) + ",";
}
q.pop();
}
return str;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
TreeNode* root = nullptr;
queue<TreeNode**> q;
q.push(&root);
string::iterator first = data.begin();
while (first != data.end()) {
TreeNode** pp = q.front();
if (*first == '#') {
// *pp = nullptr;
advance(first, 2);
} else {
string::iterator last = find(first, data.end(), ',');
int val = stoi(string(first, last));
*pp = new TreeNode(val);
q.push(&((*pp)->left));
q.push(&((*pp)->right));
first = next(last);
}
q.pop();
}
return root;
}
};

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

https://discuss.leetcode.com/topic/28092/python-preorder-recursive-traversal

Python preorder recursive traversal

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
def serialize(self, root):
preorder = ''
if not root:
preorder += ',None'
return preorder
preorder += ','+str(root.val)
preorder += self.serialize(root.left)
preorder += self.serialize(root.right)
return preorder

def deserialize(self, encode_data):
pos = -1
data = encode_data[1:].split(',')
for i in xrange(len(data)):
if data[i] == 'None':
data[i] = None
else:
data[i] = int(data[i])
root, count = self.buildTree(data, pos)
return root

def buildTree(self, data, pos):
pos += 1
if pos >= len(data) or data[pos]==None:
return None, pos

root = TreeNode(data[pos])
root.left, pos = self.buildTree(data, pos)
root.right, pos = self.buildTree(data, pos)
return root, pos

24ms, 70.13%, October 18, 2016

https://discuss.leetcode.com/topic/28029/easy-to-understand-java-solution

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}

private void buildString(TreeNode node, StringBuilder sb){
if(node == null)
sb.append(NN).append(spliter);
else{
sb.append(node.val).append(spliter);
buildString(node.left, sb);
buildString(node.right, sb);
}
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(spliter)));
return buildTree(nodes);
}

private TreeNode buildTree(Deque<String> nodes){
String val = nodes.remove();
if(val.equals(NN)) return null;
else{
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}
}

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

python

239ms, 43.88%, October 18, 2016

https://discuss.leetcode.com/topic/28041/recursive-preorder-python-and-c-o-n

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
# 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):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
def doit(node):
if node:
vals.append(str(node.val))
doit(node.left)
doit(node.right)
else:
vals.append('#')
vals = []
doit(root)
return ' '.join(vals)


def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
def doit():
val = next(vals)
if val == '#':
return None
node = TreeNode(int(val))
node.left = doit()
node.right = doit()
return node
vals = iter(data.split())
return doit()

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
谢谢你,可爱的朋友。