AcWing 1497. 树的遍历-java
原题链接
简单
作者:
Astarion
,
2021-03-09 18:39:42
,
所有人可见
,
阅读 578
import java.io.*;
import java.util.HashMap;
import java.util.Map;
class Main {
static InputStreamReader isr = new InputStreamReader(System.in);
static BufferedReader in = new BufferedReader(isr);
static OutputStreamWriter osw = new OutputStreamWriter(System.out);
static BufferedWriter out = new BufferedWriter(osw);
static int n;
//a存储后序遍历序列(LRN)
static int[] a = new int[33];
//b存储中序遍历序列(LNR)
static int[] b = new int[33];
//优化:存储节点编号在中序序列b中的位置,方便快速定位
static Map<Integer, Integer> loc = new HashMap<>();
//存储节点的左右子节点
static Map<Integer, Integer> lc = new HashMap<>();
static Map<Integer, Integer> rc = new HashMap<>();
//队列,用于层次遍历
static int head, tail;
static int[] queue = new int[33];
static int generateTree(int al, int ar, int bl, int br) {
if (al == ar) return a[ar];
//后序序列的最后一个节点是子树的root节点
int root = a[ar];
int locRoot = loc.get(root);
//左子树
if (locRoot > bl) lc.put(root, generateTree(al, al + locRoot - bl - 1, bl, locRoot - 1));
//柚子树
if (locRoot < br) rc.put(root, generateTree(al + locRoot - bl, ar - 1, locRoot + 1, br));
return root;
}
static void levelOrder(int root) throws IOException {
out.write(root+" ");
if (lc.containsKey(root)) queue[tail++] = lc.get(root);
if (rc.containsKey(root)) queue[tail++] = rc.get(root);
while (head < tail) {
root = queue[head++];
out.write(root+" ");
if (lc.containsKey(root)) queue[tail++] = lc.get(root);
if (rc.containsKey(root)) queue[tail++] = rc.get(root);
}
}
public static void main(String[] args) throws IOException {
n = Integer.parseInt(in.readLine());
String[] strs = in.readLine().split(" ");
for (int i = 0; i < n; i++) a[i] = Integer.parseInt(strs[i]);
strs = in.readLine().split(" ");
for (int i = 0; i < n; i++) {
b[i] = Integer.parseInt(strs[i]);
loc.put(b[i], i);
}
generateTree(0, n - 1, 0, n - 1);
levelOrder(a[n - 1]);
in.close();
isr.close();
out.flush();
out.close();
osw.close();
}
}