算法-7.重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
思路：首先找到当前前序的第一个节点，然后再根据该节点找到当前中序中的节点，将中序拆分成两部分，左边部分是在root的左子树，右边部分是在root的右子树。而中序的左边部分的节点个数，其实就是当前前序第一个节点后紧跟着的相同个数，而中序的右边部分的节点个数，其实就是当前前序再跳过中序左边部分的节点个数之后剩下的节点个数。即：当前前序第一个点为root，而剩下的节点分别属于root的左子树和右子树，前面部分是左子树，后面部分是右子树；找到当前中序的root点后，root点的左边部分为其左子树，右边部分为其右子树。这样就可以通过拆分子树，找到每个子树的前序遍历的第一个节点，就是对应的子树节点。
返回如下的二叉树：

     3
    / \
   9  20
     /  \
    15   7

递归实现：

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return root;
    }

    /**
     * 前序遍历 preorder = [3,9,20,15,7]
     * 中序遍历 inorder = [9,3,15,20,7]
     * {1,2,4,7,3,5,6,8}
     * {4,7,2,1,5,3,8,6}
     * @param pre
     * @param startPre
     * @param endPre
     * @param in
     * @param startIn
     * @param endIn
     * @return
     */
    private static TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn) {
            return null;
        }
        TreeNode root = new TreeNode(pre[startPre]);

        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == pre[startPre]) {

                // 比如此时i=3
                // 左边的新的前序的开始和结束：startPre = 0：startPre + 1 = 1；startPre + i - startIn = 0 + 3 - 0 = 3
                // 左边的新的中序的开始和结束：startIn = 0；i - 1 = 3 - 1 = 2
                // 右边的新的前序的开始和结束：新的startPre=i-startIn是新的中序的开始

                // 第一次递归，左边子树的递归
                // 此时startPre = 1， endPre = 3  startIn = 0  endIn = 2
                // 当i=2时，元素是2
                // 此时右边子树再次递归的话，startPre = 2 endPre = 3
                // startIn = 3  endPre = 2

                // 比如第一次递归，右边子树的递归
                // 此时startPre = 4  endPre = 7  startIn = 4  endIn = 7
                // 当i=5的时候，元素是3
                // 5-4+4+1是右子树的右子树的递归的startPre
                // 经过中序找到与前序的第一个点一致的点后，将中序拆分成两个新的中序
                // 左边的中序为root的left来递归，右边的中序为root的right来递归
                // 前序剩下的节点中，与紧接着的与中序左边个数相同的个数为左边递归的前序，剩下的为右边前序
                root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                // i - startIn为中序的起始点到找到的点的个数，那么中序再拆分之后，右边递归的起始点就需要+1
                // 而前序就需要加1之后再跳过这么多个左边的节点
                root.right = reConstructBinaryTree(pre, startPre + 1 + i - startIn, endPre, in, i + 1, endIn);
            }
        }
        return root;
    }