【剑指7】重建二叉树

题目描述：

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

分析：

如图所示，前序遍历序列的第一个数字1就是根节点的值。扫描中序遍历序列，就能确定根节点的值的位置。根据中序遍历的特点，在根节点的值1前面3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。

image.png

在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但在中序遍历中，根节点的值在序列的中间，左子树的结点的值位于根节点的值的左边，而右子树的结点的值位于根节点的右边。因此我们需要扫描中序遍历序列，才能找到根节点的值。

由于中序遍历序列中，有3个数字是左子树结点的值，因此左子树总共有3个左子结点。同样，在前序遍历的序列中，根节点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。

image.png

public class ReconstructedBinaryTree {
    public static void main(String[] args) {
        // 二叉树的先序序列
        int[] preOrder = {1, 2, 4, 7, 3, 5, 6, 8};
        // 二叉树的中序序列
        int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6};
        BinaryTreeCode root = reconstructeTree(preOrder, inOrder);
        postOrder(root); // 后序打印二叉树

    }

    /**
     * 重建二叉树
     *
     * @param preOrder
     * @param inOrder
     * @return
     */
    public static BinaryTreeCode reconstructeTree(int[] preOrder, int[] inOrder) {
        if (preOrder == null || preOrder.length == 0 || inOrder == null || inOrder.length == 0) {
            return null;
        }
        //二叉树根节点
        BinaryTreeCode root = new BinaryTreeCode(preOrder[0]);

        //左子树数目
        int leftNum = 0;
        for (int i = 0; i < inOrder.length; i++) {
            if (preOrder[0] == inOrder[i]) {
                break;
            } else {
                leftNum++;
            }
        }

        //右子树个数
        int rightNum = preOrder.length - leftNum - 1;

        //重建左子树
        if (leftNum > 0) {
            int[] leftPreOrder = new int[leftNum];
            int[] leftInorder = new int[leftNum];
            for (int i = 0; i < leftNum; i++) {
                leftPreOrder[i] = preOrder[i + 1];
                leftInorder[i] = inOrder[i];
            }
            BinaryTreeCode leftRoot = reconstructeTree(leftPreOrder, leftInorder);
            root.setLeft(leftRoot);
        }

        //重建右子树
        if (rightNum > 0) {
            int[] rightPreOrder = new int[rightNum];
            int[] rightInOrder = new int[rightNum];

            for (int i = 0; i < rightNum; i++) {
                rightPreOrder[i] = preOrder[leftNum + 1 + i];
                rightInOrder[i] = inOrder[leftNum + 1 + i];
            }
            BinaryTreeCode rightRoot = reconstructeTree(rightPreOrder, rightInOrder);
            root.setRight(rightRoot);
        }

        return root;

    }

    /**
     * 后序遍历
     */
    public static void postOrder(BinaryTreeCode root) {
        if (root == null) return;
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue());
    }

    static class BinaryTreeCode {
        private int value;
        private BinaryTreeCode left;
        private BinaryTreeCode right;

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

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public BinaryTreeCode getLeft() {
            return left;
        }

        public void setLeft(BinaryTreeCode left) {
            this.left = left;
        }

        public BinaryTreeCode getRight() {
            return right;
        }

        public void setRight(BinaryTreeCode right) {
            this.right = right;
        }
    }

}