106.从中序与后序遍历中构造二叉树

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

示例 1:

img

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

示例 2:

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

Solution

和105如出一辙，在后序遍历中，最后一个位置就是根节点的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
         int n=inorder.length;
         Map<Integer,Integer> index=new HashMap<>();
         for (int i = 0; i < postorder.length; i++) {
            index.put(inorder[i], i);
         }
         return dfs(inorder,0,n,postorder,0,n,index);
    }
    public TreeNode dfs(int [] inorder, int inL,int inR,int [] postorder,int postL,int postR,Map<Integer,Integer> index){
        if(postL==postR){
              return null;
          }
        int leftSize=index.get(postorder[postR-1])-inL;
       // 后序遍历的左子树区间是[postL,postL+leftSize]
        TreeNode left=
            dfs(inorder,inL,inL+leftSize,postorder,postL,postL+leftSize,index);
       // 后序遍历的右子树区间是[post+leftSize,postR-1],postR是根节点的位置
        TreeNode right=
            dfs(inorder, inL+leftSize+1, inR, postorder, postL+leftSize, postR-1, index);

        return new TreeNode(postorder[postR-1],left,right);
    }
}