题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

import java.util.*;
class Main{
    // 我以为有什么好办法可以 一边dfs一边得到层序遍历只能先build tree 这里用哈希表来建树 Map left right 是一个启发点学到了
    static Map<Integer, Integer> left = new HashMap<>();
    static Map<Integer, Integer> right = new HashMap<>();
    static Map<Integer, Integer> map = new HashMap<>();
    static int[] inorder, postorder;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        postorder = new int[n];
        for (int i = 0; i < n; i++) postorder[i] = sc.nextInt();
        inorder = new int[n];
        for (int i = 0; i < n; i++) inorder[i] = sc.nextInt();
        for (int i = 0; i < n; i++) map.put(inorder[i], i);
        int root = dfs(0, n - 1, 0, n - 1);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(root);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                list.add(cur);
                if (left.get(cur) != -1) queue.offer(left.get(cur));
                if (right.get(cur) != -1) queue.offer(right.get(cur));
            }
        }
        for (int i : list) {
            System.out.print(i);
            System.out.print(' ');
        }
    }

    public static int dfs(int inLeft, int inRight, int postLeft, int postRight) {
        if (inLeft > inRight) return -1;
        int root = postorder[postRight--];
        int k = map.get(root);
        left.put(root, dfs(inLeft, k - 1, postLeft, postLeft + k - 1 - inLeft));
        right.put(root, dfs(k + 1, inRight, postLeft + k - inLeft, postRight--));
        return root;
    }
blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla