已知前序和中序结果，构建二叉树

题目

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

时间限制：1秒 空间限制：32768K

解题思路

我自从学校acm集训队退役后，好久都没有写题目了，好多都已经忘了，现在先从简单的练起吧，每天写几个

从这个题目我们可以知道前序和中序的结果，如果不知道二叉树的遍历的可以自己去查一下，前序遍历就是先输出根节点，然后再输出左子树，最后输出右子树，而中序遍历就是先输出左子树，然后输出根节点，最后输出右子树。前，中，后就是输出根节点的位置的描述。
构建树一定要从根节点找起，既然知道了前序的结果，那么我们就已经知道根节点了，然后再从中序结果里面找到根的位置，我们就可以划分出左右子树了，这样就好办了，因为左右子树我们可以将其看成一个单独的树，我们又开始找根，又开始划分它的左右子树，这样重复的行为，我们可以通过递归的方式解决问题，这样代码就很简单了。如果使用栈来解决这个问题就很复杂了。

代码示例

/**
*这是节点类，是树的一个结点
*/
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length<=0&&in.length<=0){
            return null;
        }
        return ConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    }
    
    //由于给的方法只有两个参数，递归的时候不方便，要处理数组，所以我们自己写一个方法来递归，这样就只用记住位置，而不用处理数组了
    public TreeNode ConstructBinaryTree(int [] pre, int ps, int pe, int [] in, int is, int ie){
        if(ps > pe || is > ie){
            return null;
        }
        TreeNode root = new TreeNode(pre[ps]);
        for(int i = is; i<=ie; i++){
            if(in[i] == pre[ps]){
                root.left = ConstructBinaryTree(pre, ps+1, ps+i-is, in, is, i-1);
                root.right = ConstructBinaryTree(pre, ps+i-is+1, pe, in, i+1, ie);
                break;
            }
        }
        return root;
    }
}