是个好题, 因为不会做hh
import java.util.*;
public class Main {
static int N = 40, n;
static int[] p = new int[N]; // 后序
static int[] h = new int[N]; // 先序
static int[] l = new int[N]; // 节点左儿子
static int[] r = new int[N]; // 结点右儿子
static Map<Integer, Integer> map = new HashMap<>();
public static int build(int x, int y, int x1, int y1)
{
int root = p[y1];
int t = map.get(root);
if (x < t) l[root] = build(x, t - 1, x1, x1 - x + t - 1); // 左
if (t < y) r[root] = build(t + 1, y, x1 - x + t, y1 - 1); // 右
return root;
}
public static void bfs(int x)
{
Queue<Integer> q = new LinkedList<>();
q.add(x);
while (!q.isEmpty())
{
int t = q.poll();
if (l[t] != -1) q.add(l[t]);
if (r[t] != -1) q.add(r[t]);
System.out.print(t + " ");
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i ++ ) p[i] = sc.nextInt();
for (int i = 1; i <= n; i ++ ) // 中序
{
h[i] = sc.nextInt();
map.put(h[i], i);
}
Arrays.fill(l, -1); Arrays.fill(r, -1);
int root = build(1, n, 1, n);
bfs(root);
}
}