重建二叉树

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

思路：
可以根据前序遍历序列来找到根节点,然后根据中序遍历找到对应根节点的位置.
来分割左子树和右子树.根据题目给出的序列,原型二叉树如下：

image.png

我们可以看出根左边2,4,7(4,7,2)是改树的左子树,3,5,6,8(5,3,8,6)是右子树.
整体下来就可以通过递归的思想去完成这道题,根据中序序列根结点的位置的左右序列来确定节点的左右子树.

    public TreeNode reConstructBinaryTree(int[] pre, int[] in)
    {
        if(pre == null || in == null || pre.length == 0 || in.length == 0)
            return null;

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

    /**
     * 利用递归的思想完成重建
     * 1.根节点根据preOrder确定
     * 2.左右子树通过inOrder确定
     * 3.条件root.left(preStart+1)代表左子树的起点每次在当前位置的下一个
     *       preStart+length表示:length表示左子树的长度，preStart表示pre左子树的启示位置.
     *       preStart+leftLength代表左子树的结尾,那么下一个元素就是右子树的起点
     *       preStart+length+1就代表右子树的开始位置.
     * @param pre
     * @param preStart
     * @param preEnd
     * @param in
     * @param inStart
     * @param inEnd
     * @return
     */
    private TreeNode reConstructBinaryTree(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd){
        //递归终止条件
        if(preStart > preEnd || inStart > inEnd)
            return null;
        //定义根节点
        TreeNode root = new TreeNode(pre[preStart]);
        for(int i=inStart;i<=inEnd;i++){//说明找到了根节点
            if(in[i] == pre[preStart]){
                //确定左子树长度
                int leftLength = i - inStart;
                //然后分别确定左右子树
                root.left = reConstructBinaryTree(pre,preStart+1,preStart+leftLength,in,inStart,i-1);
                root.right = reConstructBinaryTree(pre,leftLength+1+preStart,preEnd,in,i+1,inEnd);
            }
        }
        return root;
    }
}