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

前言

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

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

前序遍历
后序遍历

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

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

思路

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

代码

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.poll();
        if(cur.equals("#")) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(cur)); // 新建节点
        node.left = deserialize(queue); // 左子树
        node.right = deserialize(queue); // 右子树
        return node;
    }
}
复制代码

后序遍历序列化与反序列化

思路

用后续遍历将二叉树结构序列化为一个字符串，空节点用 # 来表示。
栈的出队顺序为先进后出，即在序列化时先添加的左子树、右子树和根节点，在经过栈存储数据后，就会变成跟前序遍历使用队列一样的构建顺序。
反序列化时用栈来存储所有节点(根据后序遍历顺序存储)，判断当前出队元素是否为 # ，如果是则为空节点，如果不是则新建树节点，并依次处理该节点的左子树和右子树。

代码

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.poll();
        if(cur.equals("#")) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(cur)); // 新建节点
        node.left = deserialize(stack); // 左子树
        node.right = deserialize(stack); // 右子树
        return node;
    }
}
复制代码

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

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

重建二叉树

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

思路

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

代码

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;
}
复制代码