leetcode106. 从中序与后序遍历序列构造二叉树(java详解版)

class Solution {
      
     
    //这里的int leftIn,int rightIn,int leftPost,int rightPost分别表示我们每层递归子树的
    //左右子树的下标范围 (分别在中序和后序数组的当中的范围)
    public TreeNode getTree(int leftIn,int rightIn,int leftPost,int rightPost,int[] in,int[] post) {
        if (leftIn > rightIn) return null;

        //确定根节点在中序数组中的下标
        int rootIn = leftIn;
        while (rootIn <= rightIn && in[rootIn] != post[rightPost]) rootIn++;

        //确定左子树中结点个数
        int leftNums = rootIn - leftIn; 

        TreeNode  root = new TreeNode(post[rightPost]);
        //确定左子树对应得坐标范围
        //这里在后序遍历出的数组中 确定左子树的范围是[leftPost,leftPost+leftNums-1]
        //这里右闭区间为啥要减1呢，举个例子 比如说确定了leftNums = 3 说明了左子树有3个结点
        //那么在后序数组中 leftpost = 0,我们想要的是在后序数组中确定三个结点，那么的话
        //其实下标就是 0，1，2  但是我们leftpos+leftNums = 4,下标就到4了所以就需要减一
        //同理推出在（后序数组）右子树范围起始位置是 leftpos+leftNums。
        root.left = getTree(leftIn,rootIn-1,leftPost,leftPost+leftNums-1,in,post);
        root.right = getTree(rootIn+1,rightIn,leftPost+leftNums,rightPost - 1,in,post);

        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
       return  getTree(0,inorder.length-1,0,postorder.length-1,inorder,postorder);
    }
}