从中序和后序构造二叉树

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

示例 1:

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

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

解法

与从中序和前序遍历构造二叉树的代码相似，参考那个即可。

代码为：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer,Integer> map = new HashMap<>(); 
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        for (int i = 0;i<n;i++){
            map.put(inorder[i],i);
        }
        return myBuildTree(inorder,postorder,0,n-1,0,n-1);
    }
    public TreeNode myBuildTree(int[] inorder, int[] postorder,int inl,int inr,int postl,int postr){
        if (inl>inr) return null;
        if (postr<postl) return null;
        //找到中序遍历中节点的位置
        int index_root = map.get(postorder[postr]);

        //构造根节点
        TreeNode root = new TreeNode(postorder[postr]);

        //右子树的数量
        int size_right = inr-index_root;


        //左
        root.left = myBuildTree(inorder,postorder,inl,index_root-1,postl,postr-size_right-1);
        //右
        root.right = myBuildTree(inorder,postorder,index_root+1,index_root+size_right,postr-size_right,postr-1);
        return root;
    }
}