剑指offer 重建二叉树 解法

// 说一下 看到有些高票解法还加了前序遍历的最后索引 这个并不需要哦 递归基只需要insta>inend就行了哦
/**
    首先明确根节点就是pre[presta]  前序遍历数组第一个哦
    算法思路就是先找到中序遍历里面找到根节点对应的索引i
    就可以确定根节点左子树，右子树的前序遍历第一个  中序遍历第一个 中序遍历最后一个
    当中序遍历第一个>中序遍历最后一个 返回Null
 *
/
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        
        if(pre==null||in==null ||pre.length!=in.length) return null;
        
        return construct(pre,in,0,0,in.length-1);
        
        
    }
    
    private TreeNode construct(int[] pre,int[] in,int presta,int insta,int inend)
    {
        if(insta>inend) return null;
        
        TreeNode root=new TreeNode(pre[presta]);
        for(int i=insta;i<=inend;i++)
        {
            if(pre[presta]==in[i])
            {
                root.left=construct(pre,in,presta+1,insta,i-1);
                root.right=construct(pre,in,presta+i-insta+1,i+1,inend);
                break;
            }
        }
        
        return root;
        
    }
    
}