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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
// 使用数组模拟指针，lc[i] 存储节点 i 的左孩子，rc[i] 存储右孩子
private static int[] lc, rc;
// 使用 StringBuilder 缓存结果
private static StringBuilder preOrder = new StringBuilder();
private static StringBuilder inOrder = new StringBuilder();
private static StringBuilder postOrder = new StringBuilder();
public static void main(String[] args) throws IOException {
// 使用 BufferedReader 和 PrintWriter 提升大规模数据下的 I/O 效率
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine().trim());
// 边界情况：空树
if (n == 0) {
return;
}
// 初始化结构：n+1 长度是为了匹配从 1 开始的节点编号
lc = new int[n + 1];
rc = new int[n + 1];
boolean[] hasParent = new boolean[n + 1]; // 用于寻找根节点（根节点没有父节点）
// 使用邻接表暂时存储“父 -> 子”的原始指向关系，随后再按规则分配左右
List<Integer>[] adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
// 读取 n-1 条边，构建树的层级关系
for (int i = 0; i < n - 1; i++) {
String[] edge = br.readLine().trim().split("\\s+");
int u = Integer.parseInt(edge[0]); // 父节点
int v = Integer.parseInt(edge[1]); // 子节点
adj[u].add(v);
hasParent[v] = true; // 只要被指向，就说明该节点不是根节点
}
/**
* 根据题目定义的规则，将 adj 里的子节点分配到 lc 或 rc
*/
for (int i = 1; i <= n; i++) {
// 父节点拥有两个孩子
if (adj[i].size() == 2) {
int c1 = adj[i].get(0);
int c2 = adj[i].get(1);
// 编号小者为左，大者为右
lc[i] = Math.min(c1, c2);
rc[i] = Math.max(c1, c2);
}
// 父节点仅有一个孩子
else if (adj[i].size() == 1) {
int child = adj[i].get(0);
// 子节点编号 > 父节点编号 ➜ 视为左孩子；反之 ➜ 视为右孩子
if (child > i) {
lc[i] = child;
} else {
rc[i] = child;
}
}
}
// 寻找整棵树的唯一根节点
int root = 1;
for (int i = 1; i <= n; i++) {
if (!hasParent[i]) {
root = i;
break;
}
}
// 从根节点开始DFS
traverse(root);
// 格式化输出
out.println(preOrder.toString().trim());
out.println(inOrder.toString().trim());
out.println(postOrder.toString().trim());
// 刷新缓冲区确保数据完整写出并关闭流
out.flush();
out.close();
br.close();
}
/**
* 深度优先遍历 (DFS) 方法
*
* @param cur 当前正在访问的节点索引
*/
private static void traverse(int cur) {
// 基准情形：如果当前节点为 0，说明触碰到了空叶子节点，停止向下延伸
if (cur == 0) {
return;
}
/**
* 1. 先序遍历 (Pre-order)：[中] -> 左 -> 右
* 刚进入当前节点时立即记录。
*/
preOrder.append(cur).append(" ");
// 向左延伸
traverse(lc[cur]);
/**
* 2. 中序遍历 (In-order)：左 -> [中] -> 右
* 当左子树全部处理完毕回溯到当前点时记录。
*/
inOrder.append(cur).append(" ");
// 向右延伸
traverse(rc[cur]);
/**
* 3. 后序遍历 (Post-order)：左 -> 右 -> [中]
* 当左右子树全部处理完毕，即将彻底离开当前点时记录。
*/
postOrder.append(cur).append(" ");
}
|
