力扣106 从中序与后序遍历序列构造二叉树

题目：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例：

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

思路：

1.空节点

2.只有根节点

3.找到根节点作为切割点

4.切割中序数组

5.切割后序数组

6.递归处理左右区间

本题最需要注意的点：（1）各分割数组边界（2）右中序数组和右后序数组的起始下标要从0开始

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {////中序：左根右  后序：左右根
        int psize=postorder.length;
        //1.空节点
        if(psize==0){
            return null;
        }
        TreeNode root=new TreeNode(postorder[psize-1]);
        //2.只有根节点
        if(psize==1){
            return root;
        }
        //3.找到根节点作为切割点
        int index;
        for(index=0;index<inorder.length;index++){
            if(inorder[index]==postorder[psize-1]){
                break;
            }
        }
        //4.切割中序数组
        int[] leftInorder=new int[index];//左中序数组
        for(int i=0;i<index;i++){
            leftInorder[i]=inorder[i];
        }
        int[] rightInorder=new int[inorder.length-index-1];//右中序数组
        for(int i=index+1;i<inorder.length;i++){
            rightInorder[i-index-1]=inorder[i];//注意：右区间的起始下标
        }
        //5.切割后序数组（与切割后对应中序数组大小一致）
        int[] leftPostorder=new int[leftInorder.length];//左后序数组、
        for(int i=0;i<index;i++){
            leftPostorder[i]=postorder[i];
        }
        int[] rightPostorder=new int[rightInorder.length];//右后序数组
         for(int i=index;i<psize-1;i++){
            rightPostorder[i-index]=postorder[i];//注意：右区间的起始下标
        }
        //6.递归处理左右区间
        root.left=buildTree(leftInorder,leftPostorder);
        root.right=buildTree(rightInorder,rightPostorder);
        return root;
    }
}