从后序序列和中序序列构造二叉树

问题陈述

1
2
3
4
5
6
7
8
9
前序序列 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

    3
   / \
  9  20
    /  \
   15   7

代码实现

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) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return buildTreeHelper(inorder,0,inorder.length-1,postorder,0,postorder.length-1,map);

    }
    public TreeNode buildTreeHelper(int[] inorder,int i_start,int i_end,int[] postorder,int p_start,int p_end,HashMap<Integer,Integer> map){
        if(postorder.length==0||inorder.length==0||p_start>p_end||i_start>i_end){
            return null;
        }
        int root_val=postorder[p_end];
        TreeNode root=new TreeNode(root_val);
        int i_root_index=map.get(root_val);
        int leftnum=i_root_index-i_start;
        root.right=buildTreeHelper(inorder,i_root_index+1,i_end,postorder,p_start+leftnum,p_end-1,map);
        
 root.left=buildTreeHelper(inorder,i_start,i_root_index-1,postorder,p_start,p_start+leftnum-1,map);
        return root;

    }
}