剑指 Offer 之重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出二叉树并输出它的头结点。

分析

利用二叉树的 前序遍历 和 中序遍历 可以构造出一棵二叉树，中序遍历 和 后序遍历 也可以构造出一棵二叉树。前序遍历 和 后序遍历 用来指定根节点的位置，中序遍历 用来指定该根节点有哪些左右子树。

拿 前序遍历 序列{1, 2, 4, 7, 3, 5, 6, 8}和 中序遍历 序列{4, 7, 2, 1, 5, 3, 8, 6}来说，具体步骤如下：

首先在 前序遍历 中第一个节点 1 就是构造后的二叉树的根节点，然后在 中序遍历 中用 1 将序列划分成 {4, 7, 2} 和 {5, 3, 8, 6} 两部分，前部分是 1 的左子树上所有的节点，后部分是 1 右子树上所有的节点。
接下来要确定 1 的左孩子。我们可以看到序列 {4, 7, 2} 在 前序遍历 中，2 是排在前面的，所以 2 是 1 的左孩子，用 2 在 中序遍历 中找到 2 的左右子树。发现在序列 {4, 7, 2, 1, 5, 3, 8, 6} 中，2 的左孩子包含 {4, 7}，而没有右孩子（因为 1 已经是根节点了）。
再看 {4, 7}在 前序遍历 序列 {1, 2, 4, 7, 3, 5, 6, 8} 中确定 2 的左孩子到底是谁。可以看到是 4，然后 4 的右孩子是 7。
1 的右子树上的节点也是重复上面的过程。

构造后的二叉树如下所示：

实现

总体上来说，构造二叉树的过程就是一个 递归 的过程，我们可以使用 递归 的方式来实现。

1.定义二叉树的结构体

声明某一节点的值，以及该节点的左右子树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


public class TreeNode<T> {
    public T val;
    public TreeNode<T> left;
    public TreeNode<T> right;

    public TreeNode(T val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

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


public class ConstructBinaryTree {
    public static TreeNode<Integer> constructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length <= 0 ||
                in.length <= 0 || pre.length != in.length) return null;
        return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    private static TreeNode<Integer> reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn) return null;
        TreeNode<Integer> root = new TreeNode<>(pre[startPre]);

        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == pre[startPre]) {
                root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                root.right = reConstructBinaryTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
                break;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode<Integer> root = constructBinaryTree(pre, in);

        List<Integer> preorder = BinaryTreeOrder.preorderRecursively(root);
        List<Integer> inorder = BinaryTreeOrder.inorderRecursively(root);
        List<Integer> postorder = BinaryTreeOrder.postorderRecursively(root);
        System.out.println(preorder);
        System.out.println(inorder);
        System.out.println(postorder);
    }
}

3.详解

总的来说，核心代码在第 5、14、15 行。

在 main 函数中，定义了一个 前序序列 和 中序序列，然后将 pre 和 in 传给 constructBinaryTree() 函数。

在 constructBinaryTree() 函数中，先判断序列是否符合规定的条件以及进行边界检查，最后返回一个reConstructBinaryTree()，里面的参数对应reConstructBinaryTree()方法的参数，分别是：前序序列的数组、前序序列的起始位置、前序序列的结束位置、中序序列的数组、中序序列的起始位置、中序序列的结束位置。因为起始下标都是从0开始的，所以结束下标就是length-1了。

在reConstructBinaryTree()方法中，同样是先进行边界条件的检查，然后第10行，用前序遍历序列的第一个节点1作为根节点，这和我们之前分析的都是一样的。for循环来遍历中序序列中的没一个节点，如果中序序列中的某一个节点与1相等，则分别进行左右子树的递归操作，在根节点的左右子树分别构建二叉树。

第14行，此时i=3，startIn=0，于是构建根节点1的左子树，里面的参数其实就是找到划分后的两部分的左右边界。分别为：前序序列的数组、在前序序列数组中下标为1的位置、在前序序列数组中下标为3的位置、中序序列的数组、在中序序列数组中下标为0的位置、在中序序列数组中下标为2的位置。

第15行用来构建1的右子树，对应中序遍历中的 {5, 3, 8, 6}这一部分。然后对每一个节点递归就可以了。

main函数的最后，使用递归的方式来遍历构建后的二叉树，输出其前序、中序和后序遍历的结果，用来检查一下是否构建成功。

Contents

分析

实现

1.定义二叉树的结构体

2.具体实现

3.详解