每天一道leetcode-106从中序与后序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder == null || inorder == null || postorder.length==0){
            return null;
        }
        return buildCore(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
    }
    private TreeNode buildCore(int[] postorder,int postSt,int postEnd,int[] inorder,int inSt,int inEnd){
        //后序遍历最后一个节点是根节点
        int rootValue = postorder[postEnd];
        TreeNode root = new TreeNode(rootValue);
        //后序序列只有根节点
        if(postSt == postEnd){
            return root;
        }
        //遍历中序序列，找到根节点的位置
        int rootInorder = inSt;
        while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd){
            rootInorder++;
        }
        //左子树的长度
        int leftLength = rootInorder - inSt;
        //后序序列中左子树的最后一个节点  这里一个tips是自己举一个简单的例子去找这个关系式
        int leftPostEnd = postSt + leftLength - 1;

        //左子树非空 左子树长度大于等于0
        if(leftLength>0){
            //重建左子树
            root.left = buildCore(postorder,postSt,leftPostEnd,inorder,inSt,rootInorder - 1);
        }
        //右子树非空 postEnd 和postSt是前序数组的结尾和开头，相减就是长度，如果左子树长度小于整个长度
        //那么说明右子树肯定 存在。那么对右子树也进行同样的构建树的操作。
        if(leftLength < postEnd - postSt){
            //重建右子树
            root.right = buildCore(postorder,leftPostEnd +1,postEnd-1,inorder,rootInorder+1,inEnd);
        }
        return root;
    }
}