题解 | #重建二叉树#

问题分析：找到在前序中数组第一个就是根，在中序中找到根，即可把数组分成两部分，左树右树。

[1,（2,4,7）,（3,5,6,8）]

[（4,7,2）,1,（5,3,8,6）]

递归问题定义：在前序为s1,e1。后序s2,s2下构建二叉树

递归边界条件：s1>s2的时候没有节点，为null

public class Solution {
    public TreeNode build(int s1, int e1, int s2, int e2, int[] pre, int[] vin){
        if(s1>e1)return null;
        TreeNode root = new TreeNode(pre[s1]);
        
        int i=s2;
        while(i <= e2 && pre[s1] != vin[i])i++;
        
        root.left = build(s1+1,s1-s2+i,s2,i-1,pre,vin);
        root.right = build(s1-s2+i+1,e1,i+1,e2,pre,vin);
        return root;
    }
  
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        return build(0,pre.length-1,0,vin.length-1,pre,vin);
    }
}