Vgbhfive's Blog

算法-二叉树的序列化与反序列化

Posted on Edited on

前言

最近在看算法这块的东西，算法这东西就是需要时不时的拿起来看一看，这样才会有思考，时常更新自己的知识库。

这篇文章主要包含两种解法：

  • 前序遍历
  • 后序遍历

至于为什么中序遍历不能，看到最后你就明白了。

前序遍历序列化与反序列化

思路

用先序遍历将二叉树结构序列化为一个字符串，空节点用 # 来表示。

反序列化时用 队列 来存储所有节点(根据先序遍历顺序存储)，判断当前出队元素是否为 # ，如果是则为空节点，如果不是则新建树节点，并依次处理该节点的左子树和右子树。

代码

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
public class Main {

    /**
     * 序列化 -> 采用前序遍历的实现 -> 根左右
     */
    public String serialize(TreeNode root) {
        if(root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    /**
     * 反序列化 -> 采用前序遍历的实现 -> 根左右
     */
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList(Arrays.asList(data.split(",")));
        return deserialize(queue);
    }
    
    private TreeNode deserialize(Queue<String> queue) {
        if (queue.isEmpty()) return null;
        String cur = queue.pop();
        if(cur.equals("#")) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(cur)); // 新建节点
        node.left = deserialize(queue); // 左子树
        node.right = deserialize(queue); // 右子树
        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
public class Main {

    /**
     * 序列化 -> 采用前序遍历的实现 -> 根左右
     */
    public String serialize(TreeNode root) {
        if(root == null) return "#";
        return serialize(root.left) + "," + serialize(root.right) + "," + root.val;
    }

    /**
     * 反序列化 -> 采用前序遍历的实现 -> 根左右
     */
    public TreeNode deserialize(String data) {
        Stack<String> stack = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserialize(stack);
    }
    
    private TreeNode deserialize(Stack<String> stack) {
        if (stack.isEmpty()) return null;
        String cur = stack.pop();
        if(cur.equals("#")) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(cur)); // 新建节点
        node.left = deserialize(stack); // 左子树
        node.right = deserialize(stack); // 右子树
        return node;
    }
}

中序遍历序列化与反序列化

按照上面的思路就会发现，因为无法在中序遍历中首先找到 根节点，因此中序遍历是无法完成二叉树序列化和反序列化操作。

重建二叉树

通过前序遍历数组和中序遍历数组来重建二叉树，听起来就很厉害，至于为什么要记录在这里，是因为我觉得他的思路很重要。

思路

通过在上面对二叉树的序列化和反序列化，我们会得到在重建二叉树时，首先找到 根节点 是非常重要的。(这与二叉树的反序列化思想一致)
因此我们可以通过 先序遍历找到根节点 ，其次在中序遍历中根据已知的根节点，就可以分别得到对应的 左子树节点数组、右子树节点数组 和 根节点 在中序遍历中的坐标位置。
很好，这样我们在第一次的调用中就可以找到 根节点、左子树 和 右子树。
那么最后就是 递归 调用，以根节点的左节点和根节点的右节点作为父节点分别找到其对应的子树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if (pre == null || pre.length == 0) {
        return null;
    }
    int pos = 0, len = pre.length, val = pre[0];
    for (;pos < len; pos++) {
        if (in[pos] == val) {
            break;
        }
    }
    TreeNode root = new TreeNode(val);
    // 根据前序遍历和中序遍历规则切分对应的数组来获得左右子树
    root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, pos+1), Arrays.copyOfRange(in, 0, pos)); // 左子树
    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, pos+1, len), Arrays.copyOfRange(in, pos+1, len)); // 右子树
    return root;
}
通过重建二叉树的思路，也就映照了中序遍历为何不能完成二叉树的反序列化操作。

总结

这几天做了好多关于 树 相关的算法题，总结下来就是在熟知常见的遍历手法基础上，增加一些 队列 和 栈 来保证节点的顺序性，这样就可以完成大部分的算法题的思路。

个人备注

此博客内容均为作者学习所做笔记，侵删！
若转作其他用途，请注明来源！