KK's blog

每天积累多一些

0%

LeetCode 297 Serialize and Deserialize Binary Tree

Posted on Edited on Disqus:

LeetCode 297 Serialize and Deserialize Binary Tree

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

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.

题目大意：

序列化和反序列化二叉树。

Python解法

算法思路：

N/A

注意事项：

  1. BFS解码，空节点也要入列，因为要转成#，且不让代码往下执行
  2. 难点是用#补充空节点，令每个非空节点必有左右儿子，这样解码就可以固定地每轮扫描两个。出列一个父节点，p扫描两个儿子且生成节点，若为#即空节点不入列，这和编码不同。主要因为编码的长度比节点数多，所以生成节点时，不需要再处理空节点。
    Line 25 - 32有重复，这里放在一起方便理解，也可以封装成函数
  3. 类型转换int和str, Python用popleft不是pop
  4. Line 11非空节点值要记得加入
  5. 空节点或空字符单独处理

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
26
27
28
29
30
31
32
33
34
35
36
def serialize(self, root):
	if not root:
		return ''
	queue = collections.deque([root])
	res = []
	while queue:
		node = queue.popleft()
		if node:
			res.append(str(node.val))
		else:
			res.append('#')
			continue

		queue.append(node.left)
		queue.append(node.right)
	return ','.join(res)

def deserialize(self, data):
	if not data:
		return None
	vals = data.split(',')
	p = 0
	root = TreeNode(int(vals[0]))
	queue = collections.deque([root])
	while queue:
		node = queue.popleft()

		p += 1
		if vals[p] != '#':
			node.left = TreeNode(int(vals[p]))
			queue.append(node.left)
		p += 1
		if vals[p] != '#':
			node.right = TreeNode(int(vals[p]))
			queue.append(node.right)
	return root

Java解法

解题思路：

BFS可以涉及三重循环

  1. q不为空
  2. 是否按层遍历
  3. 是否为图

这题不需要按层遍历，所以不用第二重。而且只是二叉树，不用第三重循环。

编码方式：

1
2
3
4
5
6
7
8
	      1
	    /   \
	   #     3
	        /  \
	       2   #
	      / \
	     #   #
=> 1,#,3,2,#,#,#

BFS解题步骤：

serialize:

  1. 建queue，然后首节点入列
  2. 进入q的非空循环，队首出列，分别加入左右子树。由于空子树也会被遍历，所以左右子树可能为空，队首为空时continue
    且val加入到结果字符串
  3. 用#代替null且删去末尾的#和，

deserialize:
这方法难实现点。用两个指针来代表遍历上一层和该层节点们。q出列的节点是上一层节点head，而idx指向的是
该层节点。这样head.left = Node(tokens[idx])就建立了它们的关系。两指针分别向后一位。每轮循环父指针
向后一位，而idx向后两位，因为有左右儿子。

  1. 建queue，然后首节点入列
  2. 进入q的非空循环，队首出列，分别生成非空左右子树，且建立父子关系。idx走两步，非空儿子加入q。

注意事项：

  1. #也要入栈，因为结果需要
  2. 解码需要一个字符串扫描指针（类全局指针），左右儿子无条件扫两位。这点DFS也是一样的。
  3. deserialize中循环条件要加入idx < tokens.length因为serialize末尾#已经删除。
  4. 字符串相等判断用equals，不用==。

Java代码：

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
public String serialize2(TreeNode root){
	if(root == null)
		return "{}";

	StringBuilder sb = new StringBuilder();
	Queue<TreeNode> q = new LinkedList<>();
	q.add(root);
	while(!q.isEmpty()) {		
		TreeNode n = q.poll();
		sb.append(n == null ? "null" : n.val);
		sb.append(",");
		if(n == null)
			continue;
		q.add(n.left);
		q.add(n.right);
	}
	String res = sb.toString().replaceAll("null", "#");
	int endIdx = res.length() - 1;
	while(res.charAt(endIdx) == ',' || res.charAt(endIdx) == '#')
		endIdx--;
	return "{" + res.substring(0, endIdx + 1) + "}";
}

public TreeNode deserialize2(String data) {
	String str = data.substring(1, data.length() - 1);
	if("".equals(str))
		return null;
	
	String[] tokens = str.split(",");
	int idx = 1;
	Queue<TreeNode> q = new LinkedList<>();
	TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
	q.offer(root);
	while(!q.isEmpty() && idx < tokens.length) {
		TreeNode head = q.poll();
		if(head == null)
			continue;
		head.left = generateChildNode(idx++, tokens, q);
		head.right = generateChildNode(idx++, tokens, q);
	}
	return root;
}

TreeNode generateChildNode(int idx, String[] tokens, Queue<TreeNode> q) {
	TreeNode root = null;
	if(idx < tokens.length && !"#".equals(tokens[idx])) {
		root = new TreeNode(Integer.parseInt(tokens[idx]));
		q.offer(root);
	}
	return root;
}

DFS算法II解题思路：

DFS的serialize很简单，但deserialize比较难。有点类似于前序遍历的递归版。因为编码时候就是前序遍历，解码时候也是先root再左右。
需要维护一个指针p来记录已处理的字符串。

编码方式：

1
2
3
4
    1
  2   3
5  6
=> 1,2,5,#,#,6,#,#,3,#,#

Java代码：

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
public String serialize(TreeNode root){
	if(root==null)
		return "#";
	String rootStr = root.val+"";
	String lStr = serialize(root.left);
	String rStr = serialize(root.right);
	return rootStr+","+lStr+","+rStr;
}

int p=0;
String[] items = null;

public TreeNode deserialize(String data){
	p = 0;
	items = null;
	return deserializeR(data);
}

public TreeNode deserializeR(String data){
	if(data==null||data.length()==0)
		return null;
	if(p>=data.length())
		return null;
	String curVal = getNext(data);
	if(curVal.equals("#"))
		return null;
	
	TreeNode newRoot = new TreeNode(Integer.parseInt(curVal));
	newRoot.left = deserializeR(data);
	newRoot.right = deserializeR(data);
	return newRoot;
}

public String getNext(String s){
	if(items==null)
		items = s.split(",");
	return items[p++];
}
Free mock interview