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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// 存储最终结果：key = 二叉树的层级（根节点在第0层），value = 该层级【最右侧】的节点值
    private HashMap<Integer, Integer> ans = new HashMap<>();
    // 预处理哈希表：key=中序数组的节点值，value=该值在中序数组的下标
    private HashMap<Integer, Integer> map = new HashMap<>();
    // 前序数组的全局遍历指针：按「根→左→右」的前序规则，依次取当前递归层的根节点，取完自增
    private int level = 0;
    
    public void buildTree(int[] preOrder, int[] inOrder, int left, int right, int i) {
        
        if (left > right) {
            return;
        }
        // 按前序顺序取根节点，通过哈希表拿到根节点在中序数组的下标index
        int index = map.get(preOrder[level++]);
        // 递归构建左子树，中序区间[left, index-1]，子节点层级 = 父层级+1
        buildTree(preOrder, inOrder, left, index - 1, i + 1);
        // 递归构建右子树，中序区间[index+1, right]，子节点层级 = 父层级+1
        buildTree(preOrder, inOrder, index + 1, right, i + 1);
        // 存入当前节点到对应层级，后存的节点会覆盖先存的 → 最终保留该层最右侧节点
        ans.put(i, inOrder[index]);
    }    



    public int[] solve (int[] preOrder, int[] inOrder) {
        for(int i=0;i<inOrder.length;i++){
            map.put(inOrder[i], i);
        }

        buildTree(preOrder,inOrder,0,preOrder.length-1,0);

        int[] temp = new int[ans.size()];

        for(int i=0;i<ans.size();i++){
            temp[i]=ans.get(i);
        }
        return temp;


    }