剑指offer-37

发表于 | 分类于

题目：序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。
将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。

二叉树节点

1
2
3
4
5
6
7
8
9
10
11
private static class BinaryTreeNode {
    private int val;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

    public BinaryTreeNode() {
    }
    public BinaryTreeNode(int val) {
        this.val = val;
    }
}

举例说明

二叉树

1
2
3
4
5
      1
  /     \
 2       3
/       / \
4       5  6

按前序遍历（只有前序遍历从根节点开始）系列化之后：

1
1,2,4,$,$,$,3,5,$,$,6,$,$,

思路

  • 以前的先序和后序遍历序列重构二叉树存在缺点：
  1. 要求二叉树中没有数值相同的结点
  2. 要求整个序列都读出后才能开始重构，如果序列是流式输入，那么就需要等待序列输出完毕才能完成二叉树的重构
  • 利用先序遍历
  1. node之间用,隔开
  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
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
import java.util.LinkedList;
import java.util.Queue;

public class _37{
    private static class BinaryTreeNode {
        private int value;
        private BinaryTreeNode left;
        private BinaryTreeNode right;

        public BinaryTreeNode() {
        }
        public BinaryTreeNode(int value) {
            this.value = value;
        }
    }


	public static String serialize(BinaryTreeNode root) {
		if (root == null) {
			return "$,";
		}
		String res = root.value + ",";
		res += serialize(root.left);
		res += serialize(root.right);
		return res;
	}

	public static BinaryTreeNode deserialize(String preStr) {
		String[] values = preStr.split(",");//按之前的分隔符，得到一个数组
		Queue<String> queue = new LinkedList<String>();
		for (int i = 0; i < values.length; i++) {
			queue.offer(values[i]);
		}
		return deserialize(queue);
	}
	
	public static BinaryTreeNode deserialize(Queue<String> queue) {
		String value = queue.poll();//移除并返问队列头部的元素(如果队列为空，返回null)
		if (value.equals("$")) {
			return null;
		}//分别递归消费这个队列
		BinaryTreeNode root = new BinaryTreeNode(Integer.valueOf(value));
		root.left = deserialize(queue);
		root.right = deserialize(queue);
		return root;
	}

    public static void main(String[] args) {
        //       1
        //    /    \
        //   2     3
        //  /    / \
        // 4    5  6
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n3.left = n5;
        n3.right = n6;
        
        String result = serialize(n1);
        System.out.println("serialize: "+result);
        BinaryTreeNode root = deserialize(result) ;
        System.out.println("deserialize: ");
        printTree(root);
    }

    public static void printTree(BinaryTreeNode node) {
        if (node != null) {
            System.out.print(node.value + " ");
            printTree(node.left);
            printTree(node.right);
        }
    }
}

序列化二叉树

> >