07-重建二叉树

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

首先先上一个结论，根据前序遍历和后序遍历无法确定一个二叉树(可以用两个节点的二叉树验证)，前序遍历和中序遍历、后序遍历和中序遍历这两种是可以确定二叉树的。

前序遍历的第一个节点是整个树的根节点，然后在中序遍历中找到根节点的位置，因为中序遍历中根节点的左边节点是属于左子树的，右边的节点是属于右子树的，这样我们就能将 根节点 左子树 右子树分开了，然后我们在左子树和右子树继续这般操作，这样就可以构建整棵树。

以题目中的遍历序列为例，前序遍历的第一个节点1是根节点，因为节点不含重复的数字，所以我们在中序遍历中查找此值，这样 4,7,2是左子树的，5,3,8,6是右子树的。前序遍历中的2,4,7是属于左子树，3,5,6,8是属于右子树的。这样一遍下来我们搞定了一个根节点，接下来递归的处理左子树和右子树即可(写的这么简略是因为我也不知道该怎么更详细的解释)。

递归算法主要有两个点，一个是结束条件，一个需要缩小问题规模。

写完代码后我们回头看，算法结束在如果该结点没有子节点了，那么就是叶子结点，就返回就可以了。

而给结点添加左右子树的过程其实就是在缩小问题的规模。

 public TreeNode buildTree(int[] pre, int[] in) {
        return buildTreeCore(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }
    private TreeNode buildTreeCore(int[] pre,int[] in,int preStart,int preEnd,int inStart,int inEnd){
        if (preStart == preEnd) {
          //如果只有一个节点了，那么肯定是叶子节点了，直接返回就好，也可以认为是根节点。
            return new TreeNode(pre[preStart]);
        }
        int index = indexOf(in, pre[preStart]); //查找根节点在中序遍历的位置
        int leftSize = index - inStart; //左子树的节点个数
        int rightSize = inEnd - index; //右子树的节点个数
        TreeNode root = new TreeNode(pre[preStart]);
        if (leftSize > 0) {
          // 如果左子树不是空的 那么就构造下
            root.left = buildTreeCore(pre, in, preStart + 1, preStart + leftSize, inStart, index - 1);
        }
        if (rightSize > 0) {
          //如果右子树不是空的 那么也构造下
            root.right = buildTreeCore(pre, in, preStart + leftSize + 1, preEnd, index + 1, inEnd);
        }
        return root;
    }
		//也可以优化为给定一个范围进行查找
    private int indexOf(int[] inorder, int target) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == target) {
                return i;
            }
        }
        return -1;
    }

比较让人头晕的是递归中的每一段前序遍历和中序遍历界限的确定。