[剑指offer] 序列化二叉树

题目描述

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

解题思路

  1. 对于序列化:使用前序遍历,递归的将二叉树的值转化为字符,并且在每次二叉树的结点不为空时,在转化val所得的字符之后添加一个’,’作为分割; 对于空节点则以 ‘#,’ 代替。
  2. 对于反序列化:将字符串按照“,”进行分割,插入到队列中,然后依次从队列中取出字符建立节点,递归创建一个二叉树。

参考代码

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
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
String Serialize(TreeNode root) {
if(root == null){
return "#,";
}
StringBuffer res = new StringBuffer(root.val + ",");
res.append(Serialize(root.left));
res.append(Serialize(root.right));
return res.toString();
}
TreeNode Deserialize(String str) {
String [] res = str.split(",");
Queue<String> queue = new LinkedList<String>();
for(int i = 0; i < res.length; i++){
queue.offer(res[i]);
}
return pre(queue);
}
TreeNode pre(Queue<String> queue){
String val = queue.poll();
if(val.equals("#"))
return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = pre(queue);
node.right = pre(queue);
return node;
}
}