【序列化二叉树】

14天阅读挑战赛
*努力是为了不平庸~
数据结构+算法=程序

算法知识点

序列化，反序列化，深度优先搜索

算法题目来源

Leetcode 序列化二叉树。

算法题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

做题思路

深度优先搜索
二叉树的序列化本质上是对其值进行编码，更重要的是对其结构进行编码。可以遍历树来完成上述任务。这里使用深度优先搜索。
如果是上图，规定序列化成这样的字符串1,2,None,Node,3,4,None,None,5,None,Node

模板代码

public class Codec {

   // Encodes a tree to a single string.
   public String serialize(TreeNode root) {
       return rserialize(root, "");
   }

   // Decodes your encoded data to tree.
   public TreeNode deserialize(String data) {
       String[] strs = data.trim().split(",");
       List<String> strArray = new LinkedList<String>(Arrays.asList(strs));
       return rdesrialize(strArray);
   }

   public String rserialize(TreeNode root, String str) {
       if (root == null) {
           str += "None,";
           return str;
       }
       str += root.val + ",";
       str = rserialize(root.left, str);
       str = rserialize(root.right, str);
       return str;
   }

   public TreeNode rdesrialize(List<String> strArray) {
       if ("None".equals(strArray.get(0))) {
           strArray.remove(0);
           return null;
       }
       TreeNode node = new TreeNode(Integer.parseInt(strArray.get(0)));
       strArray.remove(0);
       node.left = rdesrialize(strArray);
       node.right = rdesrialize(strArray);
       return node;
   }
}
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

算法复杂度

时间复杂度O（N），空间复杂度O（N）

做题思路

括号表示编码 + 递归下降解码
我们也可以这样表示一颗二叉树：
如果当前的树为空，则表示为 X
如果当前的树不为空，则表示为 ()CUR_NUM(RIGHT_SUB_TREE)，其中：
是左子树序列化之后的结果
是右子树序列化之后的结果
CUR_NUM 是当前节点的值
根据这样的定义，我们很好写出序列化的过程，后序遍历这颗二叉树即可，那如何反序列化呢？根据定义，我们可以推导出这样的巴科斯范式（BNF）：
T -> (T) num (T) | X
它的意义是：用 T 代表一棵树序列化之后的结果，| 表示 T 的构成为 (T) num (T) 或者 X，| 左边是对 T 的递归定义，右边规定了递归终止的边界条件。
因为：T 的定义中，序列中的第一个字符要么是 X，要么是 (，所以这个定义是不含左递归的
当我们开始解析一个字符串的时候，如果开头是 X，我们就知道这一定是解析一个「空树」的结构，如果开头是 (，我们就知道需要解析 (T) num (T) 的结构，因此这里两种开头和两种解析方法一一对应，可以确定这是一个无二义性的文法
我们只需要通过开头的第一个字母是 X 还是 ( 来判断使用哪一种解析方法
所以这个文法是 LL(1) 型文法，如果你不知道什么是 LL(1) 型文法也没有关系，你只需要知道它定义了一种递归的方法来反序列化，也保证了这个方法的正确性——我们可以设计一个递归函数：
这个递归函数传入两个参数，带解析的字符串和当前当解析的位置 ptr，ptr 之前的位置是已经解析的，ptr 和 ptr 后面的字符串是待解析的
如果当前位置为 X 说明解析到了一棵空树，直接返回
否则当前位置一定是 (，对括号内部按照 (T) num (T) 的模式解析

模板代码

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) {
            return "X";
        }
        String left = "(" + serialize(root.left) + ")";
        String right = "(" + serialize(root.right) + ")";
        return left + root.val + right;
    }

    public TreeNode deserialize(String data) {
        int[] ptr = {0};
        return parse(data, ptr);
    }

    public TreeNode parse(String data, int[] ptr) {
        if (data.charAt(ptr[0]) == 'X') {
            ++ptr[0];
            return null;
        }
        TreeNode cur = new TreeNode(0);
        cur.left = parseSubtree(data, ptr);
        cur.val = parseInt(data, ptr);
        cur.right = parseSubtree(data, ptr);
        return cur;
    }

    public TreeNode parseSubtree(String data, int[] ptr) {
        ++ptr[0]; // 跳过左括号
        TreeNode subtree = parse(data, ptr);
        ++ptr[0]; // 跳过右括号
        return subtree;
    }

    public int parseInt(String data, int[] ptr) {
        int x = 0, sgn = 1;
        if (!Character.isDigit(data.charAt(ptr[0]))) {
            sgn = -1;
            ++ptr[0];
        }
        while (Character.isDigit(data.charAt(ptr[0]))) {
            x = x * 10 + data.charAt(ptr[0]++) - '0';
        }
        return x * sgn;
    }
}
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

算法复杂度

时间复杂度O（N），空间复杂度O（N）