2019-03-13 重建二叉树

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

解答1 ：递归实现

    /**
     * @param pre 前序遍历
     * @param in  中序遍历
     * @return 二叉树根节点
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        /*
         * 输入合法性判断， 不能为空，先序和后序长度要一致
         */
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }

        return construct(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    /**
     * @param preArray 前序遍历
     * @param preStart 前序遍历的开始位置
     * @param preEnd   前序遍历的结束位置
     * @param inArray  中序遍历
     * @param inStart  中序遍历的开始位置
     * @param intEnd   中序遍历的结束位置
     * @return 数的根节点
     */
    private TreeNode construct(int[] preArray, int preStart, int preEnd, int[] inArray, int inStart, int intEnd) {
        if (preStart > preEnd) {
            return null;
        }

        // 取前序遍历的第一个数字就是根节点
        int value = preArray[preStart];
        // 在中序遍历中中寻找根节点
        int index = inStart;
        while (index <= intEnd && value != inArray[index]) {
            index++;
        }
        // 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常
        if (index > intEnd) {
            throw new RuntimeException("Invalid Iuput!");
        }

        // 创建当前根节点，并为根节点赋值
        TreeNode node = new TreeNode(value);
        // 左子树大小 = 中序中根节点位置 -中序中起始位置
        int leftTreeSize = index - inStart;

        // 递归调用构建当前节点的左子树
        node.left = construct(preArray, preStart + 1, preStart + leftTreeSize, inArray, inStart, index - 1);
        // 递归调用构建当前节点的右子树
        node.right = construct(preArray, preStart + leftTreeSize + 1, preEnd, inArray, index + 1, intEnd);

        return node;
    }