105. 从前序与中序遍历序列构造二叉树

package treeAndRecursion.code105;
import treeAndRecursion.TreeNode;
public class Solution {
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //作为类成员变量，省着传了
        this.preorder = preorder;
        this.inorder = inorder;
        //让全部整段去构建
        return bulid(0, preorder.length-1,0,inorder.length-1);
    }
    /**
     * 用先序遍历的一段  和 中序遍历的一段 去还原当前这一部分树（子树）
     * @param preLeft 先序遍历的左起始点
     * @param preRight 先序遍历的右结束点
     * @param inLeft 中序遍历的左起始点
     * @param inRight 中序遍历的右结束点
     * @return
     */
    public TreeNode bulid(int preLeft,int preRight,int inLeft,int inRight){
        //递归结束条件，当left > right
        if(preLeft > preRight){
            return null;
        }
        // 1 : 先序遍历是  根 左 右，所以先序遍历第一个值 preLeft 就是根
        TreeNode root = new TreeNode(preorder[preLeft]);
        // 2 : 确立了根之后。去找左右子树。
        // 2.1：因为中序遍历是 左 根 右，所以在中序遍历中找到根 mid 就是中序遍历中根的下标
        // 2.2：根左边就是左子树 inLeft ~ (mid -1)
        // 2.3：根右边就是右子树 (mid + 1) ~ inRight
        //  从inLeft开始找到mid的根
        int mid = inLeft;
        while (inorder[mid] != root.val){
            mid++;
        }
        //3：递归去生产左右子树
        //3.1 当前树的先序遍历的左子树，起止点变为 preLeft+1 ~ preLeft  + (左子树一共右多少个点)
        //3.2 那左子树右多少个点呢？可以从中序遍历中得到答案 就是 (mid-1) - inLeft + 1 个点。 右-左+1个点。右是mid -1 左是inLeft
        //3.3 中序遍历的左子树就是 inLeft ~ (mid -1)
        root.left = bulid(preLeft+1,preLeft + (mid -1)-inLeft+1,inLeft,mid-1);
        //4:去递归产生右子树
        //4.1先序遍历的右子树的起止点，就是上面先序遍历左子树的重点再+1，到 preRight
        //4.2 中序遍历右子树的起止点，就是 mid + 1 到 inRight
        root.right = bulid((preLeft + (mid -1) - inLeft+1) + 1,preRight,mid + 1,inRight);
        return root;
    }
}