剑指Offer(37) 序列化二叉树

发表于 | 分类于 | 阅读次数:

序列化二叉树

题目

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

思路

一般情况下，需要采用前/后序遍历和中序遍历才能确定一个二叉树，但是其实可以只采用前序遍历（从根节点开始），将空节点（null)输出为一个特殊符号（如“$”），就可以确定一个二叉树了。

　将二叉树序列化为字符串，就是前序遍历的过程，遇见空结点时，序列化为“$”，每个结点间使用逗号分隔开。

　　将字符串反序列化为二叉树，也使用前序遍历，遇见一个新数字(或者$)就建立一个新结点，不过需要注意的是，数字可能不只是个位数字，因此创建了一个全局Int变量index（在字符串上的移动的指针），以便于截取字符串中当前的结点值。（详见代码）

测试用例

  1. 功能测试（一个节点；左右斜树；完全二叉树；普通二叉树）
  2. 特殊测试（根节点为null）

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
/**
 * @description: 请实现两个函数，分别用来序列化和反序列化二叉树
 * @author: rhsphere
 * @since: 2019-07-25 22:05 by jdk 1.8
 */
public class SerializeBinaryTrees {
	public class TreeNode {
		int val;
		TreeNode left, right;
		public TreeNode(int val) {
			this.val = val;
		}
	}

	public String serialize(TreeNode node) {
		StringBuilder sb = new StringBuilder();
		if (node == null) {
			sb.append("$,");
		} else {
			sb.append(node.val + ",");
			sb.append(serialize(node.left));
			sb.append(serialize(node.right));
		}
		return sb.toString();
	}

	int index = 0;

	public TreeNode deserialize(String str) {
		TreeNode node = null;
		if (str == null || str.length <= 0) 
			return node;
		int start = index;
		while (str.charAt(index) != ',')
			index++;
		if (!str.substring(start, index).equals("$")) {
			node = new TreeNode(Integer.parseInt(str.substring(start, index)));
			index++;
			node.left = deserialize(str);
			node.right = deserialize(str);
		} else {
			index++;
		}
		return node;
	}
}

总结

  1. 记住这种序列化的方式，用于表示二叉树时非常方便。

  2. 字符串中有分割符号时，可以对字符串采用split()方法，变为字符串数组，但是自己觉得数组的保存会消耗一定的空间，因此自己定义了全局变量index，通过substring()方法来截取每一部分的字符串。

  3. 字符串的比较以后尽量用equal来比较。在对某字符串采用substring()方法得到的字符串用==判断会返回false。substring的==与equal()使用

  4. String 转int 类型采用 int i = Integer.parseInt( s ); 不能用Integer.valueOf(s)，这返回的是Integer对象。

  5. index++的位置一定不能放错

0%