重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

首先通过一个例子看看前序遍历和中序遍历的特点，如下二叉树

它的前序遍历和中序遍历的结果为

我们分析一下前序遍历和中序遍历的结构

我们的思路是首先根据前序遍历找到根节点的值(第一个)，接着根据找到的根节点的值，在中序遍历中找到根节点的位置，在中序遍历中根节点左边的值是它的左子树的中序遍历，右边是它的右子树的中序遍历，并且进一步可以得到左右子树的长度，根据左右子树的长度，可以在前序遍历中找到左子树的前序遍历和右子树的前序遍历，然后重复上面的过程，又可以找到左右子树的根节点的值以及相应的左右子树，以此类推，即可重建二叉树。

完整代码如下：

public class Test {
    // 二叉树的定义
    private static class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;
        public BinaryTree(int value) {
            this.value = value;
        }
    }
    // preorder 前序遍历的数组
    // inorder 中序遍历的数组
    public static BinaryTree constructBinaryTree(int[] preorder, int[] inorder) throws Exception{
        if (preorder == null || inorder == null) {
            throw new Exception("preorder or inorder is null");
        }
        return helpContructBinaryTree(preorder, 0, preorder.length - 1,
                inorder, 0, inorder.length - 1);
    }
    // 根据前序遍历数组和中序遍历数组获得根节点
    private static BinaryTree helpContructBinaryTree(int[] preorder, int preStart, int preEnd,
                               int[] inorder, int inStart, int inEnd) throws Exception{
        // 前序遍历的第一个值就是根节点
        BinaryTree root = new BinaryTree(preorder[preStart]);
        // 如果只有数组只有一个值
        if (preStart == preEnd) {
            if (inStart == inEnd && preorder[preStart] == inorder[inStart]) {
                return root;
            } else {
                throw new Exception("wrong input");
            }
        }
        // 获得中序遍历根节点的位置
        int inOrderRoot = inStart;
        for (; inOrderRoot <= inEnd; inOrderRoot++) {
            if (inorder[inOrderRoot] == root.value) {
                break;
            }
        }
        // 如果在中序遍历中没有找到根节点 则输入的数组有错误
        if (inOrderRoot > inEnd) {
            throw new Exception("wrong input");
        }
        // 左右子树的长度
        int leftLength = inOrderRoot - inStart;
        int rightLength = inEnd - inOrderRoot;
        if (leftLength > 0) {
            // 根据左子树的前序遍历和中序遍历获得左子树的根节点
            // [preStart + 1, preStart + leftLength] 左子树的前序遍历的范围
            // [inStart, inOrderRoot - 1] 左子树的中序遍历的范围
            root.left = helpContructBinaryTree(preorder, preStart + 1, preStart + leftLength,
                    inorder, inStart, inOrderRoot - 1);
        }
        if (rightLength > 0) {
            // 同左子树
            root.right = helpContructBinaryTree(preorder, preStart + leftLength + 1, preEnd,
                    inorder, inOrderRoot + 1, inEnd);
        }
        return root;
    }
}