第 94 章 树的基础与遍历¶
树比一般图多出来的性质只有两条——无环和任意两点唯一路径—— 但就这两条撑起了一整套算法。这一章讲地基：性质与判定、存储、三种遍历、 DFS 序与子树区间、直径与重心。
两点之间的关系（LCA、路径长度、树上差分）见 LCA 与树上路径。
这两章的组织逻辑：
树的性质与存储
↓
遍历（三种序） ← 一切树上算法的执行顺序
↓
┌─────────────┬──────────────┬─────────────┐
DFS 序 → 子树区间 直径 / 重心 LCA → 路径长度
（配数据结构） （全局特征） （两点关系）
↓ ↓
树链剖分（hld.md） 树上差分（lca.md）
贯穿全章的一条 Python 主线：树的高度可以达到 \(n\)（一条链）， 所以任何递归写法在 \(n \ge 10^4\) 时都会爆栈。 本章的每一个模板都是非递归的，而且尽可能把循环下沉到 C 层。
1 树的性质与判定¶
树：\(n\) 个点、无环、连通的无向图。
「三选二」定理¶
对一个有 \(n\) 个点、\(m\) 条边的无向图，下面三条里任意两条成立就能推出第三条， 此时图是树：
所以判定一个图是不是树，最省事的写法是：数边数 + 判连通。
# [片段] 判树：最省事的两条件写法
# m == n - 1 且连通 <=> 是树
ok = (m == n - 1) and count_components(n, start, adj) == 1
⚠️ 只判 \(m = n-1\) 是不够的：一个三角形加一个孤立点也是 4 点 3 边， 但它既不连通也有环。必须配上连通性判定（BFS 或并查集）。
基本性质表¶
| 性质 | 说明 |
|---|---|
| 任意两点间有唯一简单路径 | 这是树上一切「路径问题」的基础 |
| 加任意一条非树边 | 恰好产生一个环（次小生成树就靠这条，见 最小生成树 §6） |
| 删任意一条树边 | 恰好分成两个连通块 |
| 度数和 | \(\sum \deg(v) = 2(n-1)\)，所以平均度数 \(< 2\) |
| 叶子 | \(\deg(v) = 1\) 的点；\(n \ge 2\) 的树至少有 2 个叶子 |
| 树一定是二分图 | 无环 ⟹ 无奇环（二分图） |
| 树的直径端点 | 一定是叶子 |
| \(n\) 个带标号点的不同树的个数 | \(n^{n-2}\)（Cayley 公式），配 Prüfer 序列 |
有根树与无根树¶
题目给的边通常是无向的（「\(x\) 与 \(y\) 相连」），
而绝大多数算法需要有根树（父亲、儿子、深度、子树）。
「定根」这个动作只是选一个点当根，然后一次遍历确定所有 parent：
| 概念 | 定义 |
|---|---|
par[u] |
\(u\) 的父亲；根的父亲设为 0（哨兵，省掉边界判断） |
dep[u] |
根到 \(u\) 的边数（或点数，看题目约定） |
sz[u] |
子树 \(u\) 的点数 |
| 换根 | 把根从 \(u\) 换到相邻的 \(v\)：\(sz'[v] = n\)，\(sz'[u] = n - sz[v]\)。这是「换根 DP」的核心 |
怎么找根： - 题目直接给（BISHI124 的 \(R\)）； - 有向父子边给出 ⟹ 入度为 0 的点（BISHI96）； - 无根树且答案与根无关 ⟹ 随便取 1 号点。
2 树的存储¶
| 方式 | 结构 | 适用 |
|---|---|---|
父数组 par[] |
一个长 \(n+1\) 的 list |
只需向上跳（并查集式、LCA 倍增） |
儿子表 kids[u] |
[[] for _ in range(n+1)] |
\(n \le 10^5\) 的有根树，最好写 |
CSR（start + adj） |
两个扁平数组 | \(n \ge 2\times10^5\) 必用（图的表示与遍历 §2） |
二叉树 left[] / right[] |
两个长 \(n+1\) 的 list |
二叉树专用（BISHI96），左右有序 |
| BFS 序 + 父数组 | order[] + par[] |
树上 DP 的最优表示（94.4） |
二叉树千万不要写成节点类：
# [片段] ❌ 竞赛里不要这么写
class Node: # n = 1e5 时是 1e5 个对象，慢且费内存
def __init__(self, val):
self.val, self.left, self.right = val, None, None
竞赛里点就是编号 \(1..n\)，用 left = [0] * (n+1)、right = [0] * (n+1) 两个数组，
0 表示空。下标访问比属性访问快一倍，内存少一个数量级。
3 二叉树的三种遍历（迭代实现）¶
| 遍历 | 顺序 | 特征 |
|---|---|---|
| 先序（preorder） | 根 → 左 → 右 | 第一个元素是根 |
| 中序（inorder） | 左 → 根 → 右 | BST 的中序是有序的 |
| 后序（postorder） | 左 → 右 → 根 | 最后一个元素是根；「先处理儿子」的场合 |
为什么必须写迭代版¶
一棵二叉树可以退化成一条长度 \(n\) 的链（\(1\to2\to3\to\cdots\to n\)）， 此时递归深度就是 \(n\)：
| 问题 | 后果 |
|---|---|
| CPython 默认递归上限 1000 | \(n \ge 1000\) 的链必 RecursionError |
sys.setrecursionlimit(200000) |
只改计数器，C 栈仍会溢出 → 段错误，没有任何报错 |
| 每层递归约 0.5 μs | 比迭代慢 2–3 倍 |
判据：二叉树遍历的递归深度上界就是 \(n\)。 BISHI96 的 \(n \le 10^5\) 已经远超上限，所以三种遍历全部必须迭代。 （另一条路是
threading.stack_size(1<<26)+ 开大栈线程，但要多起一个线程、 代码更绕，这里一律用显式栈。）
模板一：先序 —— 栈里先压右后压左¶
def preorder_iter(root, left, right):
"""先序遍历（根 左 右）的迭代版。O(n)。
栈是后进先出，所以要「先压右孩子再压左孩子」，弹出时才是左先右后。
"""
out = []
st = [root] # 显式栈代替递归，深度不再受 CPython 限制
while st:
u = st.pop()
out.append(u) # 出栈即访问
r = right[u]
if r: # 0 表示空孩子，不入栈
st.append(r) # ★ 先压右
l = left[u]
if l:
st.append(l) # ★ 后压左（先弹出）
return out
模板二：中序 —— 一路向左压栈¶
def inorder_iter(root, left, right):
"""中序遍历（左 根 右）的迭代版。O(n)。
三步循环：一路向左把节点全压进栈 -> 弹出并访问 -> 转向它的右子树。
"""
out = []
st = [] # 栈里存「已进入、但左子树还没处理完」的点
u = root # u = 下一棵待展开的子树的根，0 表示空
while st or u: # 栈空且无待展开子树时才算结束
while u: # ① 一路向左
st.append(u)
u = left[u] # 走到最左端，那里是中序的第一个点
u = st.pop() # ② 弹出即访问（它的左子树已处理完）
out.append(u)
u = right[u] # ③ 转向右子树；为 0 则下轮直接再弹栈
return out
模板三：后序 —— 「根右左」再整体反转¶
def postorder_iter(root, left, right):
"""后序遍历（左 右 根）的迭代版。O(n)。
技巧：先按「根 右 左」跑一遍先序（把先序模板的左右压栈顺序对换），
得到的序列整体 reverse 就是「左 右 根」。
比「双栈法」和「标记访问次数法」都更短、更快。
"""
out = []
st = [root]
while st:
u = st.pop()
out.append(u) # 此刻 out 正在按「根 右 左」增长
l = left[u]
if l:
st.append(l) # ★ 与先序相反：先压左
r = right[u]
if r:
st.append(r) # 后压右（先弹出）
out.reverse() # ★ 一次 C 层反转
return out # 「根右左」的逆序恰好是「左右根」
三种后序迭代写法的对比（这是本节最值钱的取舍）：
| 写法 | 原理 | 代码量 | Python 速度 |
|---|---|---|---|
「根右左」+ reverse() |
先序模板对换左右，最后反转 | 最短 | ✅ 最快（reverse 在 C 层） |
| 双栈法 | 一个栈做「根右左」，另一个栈收集 | 中 | ⚠️ 多一个栈的 append/pop |
标记法 (u, visited) |
栈里存二元组，第二次遇到才访问 | 长 | ❌ 每个点造一个元组，慢 2 倍 |
为什么「根右左 + 反转」是对的：「根右左」的逆序是「左右根」—— 逆序会把「根在最前」变成「根在最后」，同时把「右在左前」变成「左在右前」， 正好是后序。一分钟就能在三节点的树上手验。
层序遍历¶
层序（BFS）就是 94.4 的 order，一个列表当队列即可：
# [片段] 层序遍历
out = [root] # 结果和队列合二为一
for u in out: # 列表在迭代中扩展是安全的
if left[u]: # 队列只在尾部追加、指针只往前走，
out.append(left[u]) # 所以 for 的内部游标不会失效
if right[u]:
out.append(right[u]) # 先左后右 -> 同层内保持左右次序
由遍历序列重建二叉树¶
| 已知 | 能唯一重建吗 | 原因 |
|---|---|---|
| 先序 + 中序 | ✅ | 先序首元素是根，在中序里定位它 ⟹ 左右子树的规模确定 |
| 后序 + 中序 | ✅ | 后序末元素是根，同理 |
| 层序 + 中序 | ✅ | 同理 |
| 先序 + 后序 | ❌ | 无法区分「只有左孩子」和「只有右孩子」 |
| 单独任一种 | ❌ | 显然 |
中序是重建的关键：只有中序能把「根左边」和「根右边」切开。 实现时把中序的「值 → 下标」预处理成
dict， 否则每层都要list.index扫一遍，退化成 \(O(n^2)\)。
4 「reversed(BFS 序) 就是后序」¶
这是 Python 里写树上 DP 的标准姿势，重要程度不亚于任何一个模板。
BFS 序里，父亲一定排在所有儿子之前。 所以倒着遍历 BFS 序，就等价于「所有儿子都处理完之后再处理父亲」—— 也就是后序 / 自底向上。
def bfs_order(n, start, adj, root=1):
"""求 BFS 序与父亲数组（CSR 存图）。O(n)，无递归、无栈、无 deque。
order 里父亲一定排在儿子前面，因此 reversed(order) 就是一个合法后序。
★ `for u in order:` 一边迭代一边 append —— BFS 只在尾部追加，安全。
"""
par = [0] * (n + 1) # par[root] = 0，0 号点当「没有父亲」的哨兵
vis = bytearray(n + 1)
vis[root] = 1
order = [root] # 结果和队列合二为一
for u in order:
for i in range(start[u], start[u + 1]):
v = adj[i]
if not vis[v]: # 树上唯一的「回头路」就是父亲
vis[v] = 1
par[v] = u # 建立父子关系，无根树就此定向
order.append(v)
return order, par
def subtree_size(n, order, par):
"""子树大小。倒着扫一遍 BFS 序即可，O(n)。"""
sz = [1] * (n + 1) # 每个点先把自己算 1
for u in reversed(order): # ★ 儿子一定已经算完
p = par[u]
if p: # 根的 par 是 0，到根就不再往上累加
sz[p] += sz[u] # 把自己整棵子树的规模并给父亲
return sz
| 三种「自底向上」写法 | 深度限制 | 速度 | 评价 |
|---|---|---|---|
| 递归 DFS | ❌ \(n \ge 1000\) 爆栈 | 慢 | 只能写小数据 |
迭代 DFS + (u, leaving) 事件栈 |
✅ | 中（每点一个元组） | 需要「进入/离开」两个时机时才用 |
| BFS 序倒序 | ✅ | 最快（两个纯数组循环） | ✅ 树上 DP 的默认写法 |
它能做什么：子树大小、子树权值和、树形 DP（没有上司的舞会、树上背包）、 树上差分的「子树求和」收尾、直径的树形 DP…… 凡是「先算儿子再算父亲」的都能用。见 DFS 深度优先搜索 §4 与 树形 DP。
它不能做什么：子树区间。BFS 序里一棵子树的点不连续， 要连续区间必须用 DFS 先序（见下一节）。
5 DFS 序与子树区间¶
三种「序」必须分清¶
| 名称 | 长度 | 每个点出现几次 | 核心性质 | 主要用途 |
|---|---|---|---|---|
DFS 序 / 先序 / dfn |
\(n\) | 1 次（进入时） | 子树 = 连续区间 | 子树改 → 区间改 |
| 括号序 | \(2n\) | 2 次（进入 + 离开） | 祖先关系 = 括号嵌套 | 判祖先、树上莫队 |
| 欧拉序 | \(2n-1\) | \(\deg\) 次（每次回溯都记） | 两点间必经过 LCA | LCA → RMQ（94.9） |
⚠️ 这三个名字在不同资料里混用得很厉害，看到「DFS 序」时一定确认长度： 长度 \(n\) 是先序，\(2n\) 是括号序，\(2n-1\) 是欧拉序。 LCA 用的是欧拉序（\(2n-1\)），这是最容易搞错的一处。
DFS 先序与子树区间¶
def dfs_order(n, start, adj, root=1):
"""DFS 先序（迭代）与子树大小。O(n)。返回 (tin, sz, seq, par)。
tin[u] = u 在先序里的下标（0-indexed），seq[tin[u]] == u。
★ 关键性质：子树 u 恰好对应连续区间 [tin[u], tin[u] + sz[u] - 1]。
因为栈式先序会把 u 的整棵子树连续地弹出。
"""
par = [0] * (n + 1)
tin = [0] * (n + 1)
seq = [] # seq = 先序序列本身
vis = bytearray(n + 1)
vis[root] = 1
st = [root]
while st:
u = st.pop() # 栈顶 = 最近压入 -> 优先往深处走
tin[u] = len(seq) # 当前长度就是 u 的先序下标
seq.append(u)
for i in range(start[u], start[u + 1]):
v = adj[i]
if not vis[v]:
vis[v] = 1 # 入栈即标记，同一点不会被压两次
par[v] = u
st.append(v)
sz = [1] * (n + 1)
for u in reversed(seq): # 先序倒序 = 后序
p = par[u]
if p:
sz[p] += sz[u]
return tin, sz, seq, par
def is_ancestor(u, v, tin, sz):
"""u 是否是 v 的祖先（含 u == v）。O(1)。"""
# u 的子树占据先序区间 [tin[u], tin[u]+sz[u])，v 落在里面就是它的后代
return tin[u] <= tin[v] < tin[u] + sz[u]
子树区间这条性质把「树上问题」变成了「序列问题」：
| 树上操作 | 序列操作 | 用什么 |
|---|---|---|
| 子树 \(u\) 整体加 \(k\) | 区间 \([tin_u,\ tin_u+sz_u-1]\) 加 \(k\) | 树状数组 / 线段树 |
| 查询子树 \(u\) 的权值和 | 区间求和 | 同上 |
| 单点改 + 子树查 | 单点改 + 区间查 | 树状数组 |
| 路径操作 | ⚠️ 不能直接映射 | 需要树链剖分（树链剖分） |
「子树 = 区间」很容易，「路径 = 区间」很难，这就是树链剖分存在的理由： 它把每条路径拆成 \(O(\log n)\) 段连续区间。 树剖的
id[u]同时也是一种 DFS 序，所以子树操作和路径操作能共用同一棵数据结构。
6 树的直径¶
直径：树上最长的简单路径（的长度）。
做法一：两次 BFS（无权树 / 非负权）¶
从任意点出发 BFS，找到最远点 \(a\)；再从 \(a\) 出发 BFS，找到最远点 \(b\)。 则 \(a \to b\) 就是一条直径。
def tree_diameter_bfs(n, start, adj):
"""两次 BFS 求树的直径（无权树）。返回 (直径边数, 端点 a, 端点 b)。O(n)。
⚠️ 正确性依赖「边权非负」。有负权边时这个结论不成立，必须用树形 DP。
"""
def farthest(s):
"""从 s 出发 BFS，返回 (最远点, 该距离)。"""
dist = [-1] * (n + 1) # -1 兼任未访问标记
dist[s] = 0
q = [s] # 列表当队列：BFS 只在尾部追加
for u in q:
d = dist[u] + 1
for i in range(start[u], start[u + 1]):
v = adj[i]
if dist[v] < 0: # 树上不需要父亲判断，标记就够
dist[v] = d
q.append(v)
m = max(dist) # ★ max / index 都在 C 层
return dist.index(m), m # 有并列时取下标最小的，任选一个都对
a, _ = farthest(1) # 第一次：从任意点找到一个直径端点 a
b, d = farthest(a) # 第二次：从 a 出发，最远点就是另一端 b
return d, a, b
正确性证明（反证）：设真正的直径是 \((s,t)\)，从任意点 \(x\) 出发的最远点是 \(a\)。 若 \(a\) 不是任何直径的端点，考察 \(x \to a\) 与 \(s \to t\) 这两条路径：
- 若它们相交于点 \(p\)，则 \(d(p,a) \ge d(p,s)\)（否则 \(x\to s\) 比 \(x\to a\) 更远）， 于是把 \(s\) 换成 \(a\) 得到的路径不比直径短，矛盾（\(a\) 也是直径端点）；
- 若它们不相交，设连接两条路径的最短路是 \(p\to q\)（\(p\) 在 \(x\to a\) 上，\(q\) 在 \(s\to t\) 上）， 则 \(d(p,a) \ge d(p,q)+d(q,s)\)，于是 \(d(a,t) = d(a,p)+d(p,q)+d(q,t) \ge d(s,q)+d(q,t) = d(s,t)\)， 同样说明 \(a\) 是直径端点。
⚠️ 有负权边时两次 BFS 就是错的（上面的不等式全部依赖非负性）。 竞赛里「树的直径 + 负权」不算罕见，看到负权立刻换树形 DP。
做法二：树形 DP（边权可负）¶
对每个点 \(u\)，「经过 \(u\) 的最长路径」= \(u\) 向下的最长链 + 次长链：
def tree_diameter_dp(n, start, adj, wt=None, root=1):
"""树形 DP 求直径（边权可为负）。O(n)。用 BFS 序倒序代替递归。
down[u] = 从 u 向下走的最长链长度（允许长度 0，即停在 u）。
技巧：处理 u 的每个孩子 v 时，down[u] 里存的是「已处理过的孩子中的最长」，
所以 down[u] + (down[v] + w) 就是「次长 + 最长」，
★ 先更新答案，再更新 down[u]，一趟就同时拿到最长和次长。
"""
order, par = bfs_order(n, start, adj, root)
down = [0] * (n + 1) # 初值 0 = 「停在 u 不往下走」也是合法的链
best = 0
for u in reversed(order): # 倒序 = 后序，孩子的 down 已经是终值
du = down[u] # 局部变量累积，最后一次性写回
for i in range(start[u], start[u + 1]):
v = adj[i]
if v == par[u]:
continue # 树上不走回父亲，就等于只看孩子
cand = down[v] + (1 if wt is None else wt[i]) # 经 v 往下的链长
if du + cand > best: # ★ 先算答案（此时 du 是次长候选）
best = du + cand # du 来自之前的孩子，与 cand 分属两个方向
if cand > du: # 再更新最长
du = cand
down[u] = du
return best # 答案是「经过某个点的最长路径」的最大值
| 两次 BFS | 树形 DP | |
|---|---|---|
| 复杂度 | \(O(n)\)（两遍） | \(O(n)\)（一遍） |
| 负权边 | ❌ 不正确 | ✅ |
| 能得到直径的端点 | ✅ 直接给出 | ⚠️ 要额外记录 |
| 代码量 | 短 | 中 |
| Python 常数 | 小（两次纯 BFS） | 小 |
| 顺便求「每点的最远距离」 | ⚠️ 要两遍 BFS 后取 max | ✅ 换根 DP 一并求出 |
默认选两次 BFS：更短、更好写、端点直接拿到。 只有出现负权或需要「每个点的最长链」时才上树形 DP。
7 树的重心与树的中心¶
这两个概念长得像，完全不是一回事：
| 重心（centroid） | 中心（center） | |
|---|---|---|
| 定义 | 删掉它后，最大子树的点数最小 | 到最远点的距离最小 |
| 等价刻画 | 使 \(\sum_v d(u,v)\) 最小的点 | 直径的中点 |
| 个数 | 1 个或 2 个（相邻） | 1 个或 2 个（相邻） |
| 求法 | 一遍求 sz，再扫一遍 |
求出直径路径，取中点 |
| 主要用途 | 点分治、树的平衡分解 | 「最小化最远距离」类题 |
def tree_centroid(n, start, adj, order, par, sz):
"""树的重心：删掉它后最大连通块的点数最小。返回 (重心, 该最小值)。O(n)。
删掉 u 之后的连通块有两类：
- 每个孩子 v 的子树，大小 sz[v]；
- 「父亲那一侧」，大小 n - sz[u]。
"""
best_node = 1
best_val = n + 1 # 比任何可能的块大小都大，保证首轮被刷新
for u in range(1, n + 1):
mx = n - sz[u] # ★ 父亲那一侧：总点数减去 u 的子树
# u 是根时它等于 0，天然正确
for i in range(start[u], start[u + 1]):
v = adj[i]
if v != par[u] and sz[v] > mx: # 跳过父亲，其余邻居都是孩子
mx = sz[v] # mx = 删掉 u 后最大的那块
if mx < best_val:
best_val = mx
best_node = u
return best_node, best_val # best_val <= n//2 是重心的特征性质
重心的性质（点分治的正确性来源）：
| 性质 | 说明 |
|---|---|
| 最大子树大小 \(\le \lfloor n/2 \rfloor\) | 所以点分治的递归深度是 \(O(\log n)\) |
| 以重心为根时，所有子树大小 \(\le n/2\) | 同上 |
| 重心到所有点的距离和最小 | 「选一个点使总距离最小」直接找重心 |
| 两棵树合并后，新重心在原两个重心的路径上 | 增量维护重心 |
| 有两个重心 ⟺ 存在一条边把树分成两个 \(n/2\) | \(n\) 必为偶数 |
BISHI101「从所有叶子出发的多源 BFS」求的是「到最近叶子距离最大的点」， 那个点集与树的中心有关但并不相同——它是「内部深度」的最大点。 见 BFS广度优先搜索。
8 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI96 | 先序遍历、中序遍历和后序遍历 | 简单 | 题解 |
| BM23 | 二叉树的前序遍历 | 简单 | 题解 |
| BM24 | 二叉树的中序遍历 | 中等 | 题解 |
| BM25 | 二叉树的后序遍历 | 简单 | 题解 |
| BM26 | 求二叉树的层序遍历 | 中等 | 题解 |
| BM27 | 按之字形顺序打印二叉树 | 中等 | 题解 |
| BM28 | 二叉树的最大深度 | 简单 | 题解 |
| BM29 | 二叉树中和为某一值的路径(一) | 简单 | 题解 |
| BM30 | 二叉搜索树与双向链表 | 中等 | 题解 |
| BM31 | 对称的二叉树 | 简单 | 题解 |
| BM32 | 合并二叉树 | 简单 | 题解 |
| BM33 | 二叉树的镜像 | 简单 | 题解 |
| BM34 | 判断是不是二叉搜索树 | 中等 | 题解 |
| BM35 | 判断是不是完全二叉树 | 中等 | 题解 |
| BM39 | 序列化二叉树 | 较难 | 题解 |
| BM40 | 重建二叉树 | 中等 | 题解 |
| BM41 | 输出二叉树的右视图 | 中等 | 题解 |
| BM36 | 判断是不是平衡二叉树 | 简单 | 题解 |
| LC94 | 二叉树的中序遍历 | 简单 | 题解 |
| LC104 | 二叉树的最大深度 | 简单 | 题解 |
| LC98 | 验证二叉搜索树 | 中等 | 题解 |
| LC101 | 对称二叉树 | 简单 | 题解 |
| LC105 | 从前序与中序遍历序列构造二叉树 | 中等 | 题解 |
| LC108 | 将有序数组转换为二叉搜索树 | 简单 | 题解 |
| LC114 | 二叉树展开为链表 | 中等 | 题解 |
| LC226 | 翻转二叉树 | 简单 | 题解 |
| LC230 | 二叉搜索树中第 K 小的元素 | 中等 | 题解 |
| LC437 | 路径总和 III | 中等 | 题解 |
| LC543 | 二叉树的直径 | 简单 | 题解 |
BISHI96 先序遍历、中序遍历和后序遍历（简单）¶
给定 \(n\ (\le 10^5)\) 个节点的二叉树，以 \(n-1\) 条有向边 \((a_i,b_i)\) 给出 （父 \(a_i\) 指向子 \(b_i\)）。左右关系的规定是： - 父节点有两个孩子 ⟹ 编号较小者为左孩子，较大者为右孩子； - 父节点只有一个孩子，且该孩子编号大于父节点编号 ⟹ 视为左孩子；否则为右孩子。
输出先序、中序、后序遍历序列。 题面见 原题。 题解见
solutions/nowcoder/BISHI96/sol.py（已通过官方样例验证）。
这题的难点全在两处：左右孩子的规则，和 \(n = 10^5\) 的递归深度。
先把规则整理成表（读错这张表就全错，且样例查不出来）：
| 情况 | 左孩子 | 右孩子 |
|---|---|---|
| 两个孩子 \(x < y\) | \(x\)（小的在左） | \(y\) |
| 一个孩子 \(v\)，且 \(v > u\) | \(v\) | 空 |
| 一个孩子 \(v\)，且 \(v < u\) | 空 | \(v\) |
⚠️ 判定基准是「孩子编号 vs 父节点编号」，不是「孩子编号 vs 兄弟」， 也不是「独子固定放左边」。两个孩子时比的是兄弟之间， 一个孩子时比的是和父亲——两条规则的比较对象不同，这是本题唯一的阅读陷阱。
根 = 入度为 0 的点（没有出现在任何 \(b_i\) 里）。
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
left = [0] * (n + 1) # 0 表示空，别用节点类
right = [0] * (n + 1)
kids = [[] for _ in range(n + 1)]
has_parent = bytearray(n + 1) # 用来找根
p = 1
for _ in range(n - 1):
a = int(data[p]); b = int(data[p + 1]); p += 2
kids[a].append(b)
has_parent[b] = 1
for u in range(1, n + 1): # ---- 按规则定左右 ----
ch = kids[u]
if len(ch) == 2:
x, y = ch
if x > y:
x, y = y, x
left[u], right[u] = x, y # 两个孩子：小的在左
elif len(ch) == 1:
v = ch[0]
if v > u:
left[u] = v # 独子且编号 > 父 -> 左
else:
right[u] = v # 否则 -> 右
root = 1
for u in range(1, n + 1): # 入度为 0 的点就是根
if not has_parent[u]:
root = u
break
# ---- 先序：根 左 右（栈里先压右再压左）----
pre = []
st = [root]
while st:
u = st.pop()
pre.append(u)
r = right[u]
if r:
st.append(r)
l = left[u]
if l:
st.append(l)
# ---- 中序：一路向左压栈，弹出访问后转右子树 ----
ino = []
st = []
u = root
while st or u:
while u:
st.append(u)
u = left[u]
u = st.pop()
ino.append(u)
u = right[u]
# ---- 后序：按「根 右 左」跑先序，再整体逆序 ----
post = []
st = [root]
while st:
u = st.pop()
post.append(u)
l = left[u]
if l:
st.append(l)
r = right[u]
if r:
st.append(r)
post.reverse() # ★ 一次 C 层反转
w = sys.stdout.write
w(" ".join(map(str, pre)) + "\n")
w(" ".join(map(str, ino)) + "\n")
w(" ".join(map(str, post)) + "\n")
main()
复杂度：建树 \(O(n)\)，三次遍历各 \(O(n)\)。\(n = 10^5\) 瞬间完成。
样例复核（这类题一定要手验）：\(n=2\)，边 \(1\to2\)。 父 1 只有一个孩子 2，且 \(2 > 1\) ⟹ 左孩子。 先序 \(=1\ 2\)；中序 \(=\) 左(2) 根(1) \(= 2\ 1\)；后序 \(=\) 左(2) 根(1) \(= 2\ 1\)。与样例一致 ✓
四个坑：
- 三种遍历全部必须迭代。这棵树可以是 \(1\to2\to\cdots\to10^5\) 的链，
递归深度 \(10^5\)；即使
setrecursionlimit调大，C 栈也会崩（无报错的段错误）； - 独子的判定基准是父节点编号（见上面的阅读陷阱）；
- \(n = 1\) 时没有任何边，
kids全空、has_parent全 0， 根取到 1，三行都输出1。代码天然处理，但一定要在脑子里跑一遍； - 输出必须先
join再一次write。三行各 \(10^5\) 个数， 逐个print会有 \(3\times10^5\) 次系统调用级开销 （输入输出处理）。
为什么后序用「根右左 + reverse」而不是双栈：见本章 §3 的对比表。 一次 C 层
list.reverse()比多维护一个栈快，代码也短 5 行。 同一份代码，三个遍历只差左右压栈顺序和一次反转——这是本题最优雅的地方。
面试题单里的十九道二叉树题¶
先说一句适用范围：这一批题的数据规模普遍在 \(10^2\) 量级 （例如二叉树的前序遍历的题面写着 \(n \le 100\)）， 递归写法在这个规模下完全能过。本章坚持非递归模板，是为了同一道题被放大到 \(n \ge 10^4\) 时不用重写——两件事不冲突，规模决定用哪一版。
三种遍历，正好对上 §3 的三个模板。
BM23 二叉树的前序遍历用模板一（栈里先压右后压左），
二叉树的中序遍历（同一道题在另一处题库里编号 LC 94. 二叉树的中序遍历）用模板二（一路向左压栈），
二叉树的后序遍历用模板三（按「根右左」遍历后整体反转）。
三题的骨架是同一份代码，差别只在压栈顺序与最后要不要 reverse()。
层序及其变形，对上 §3 的层序遍历那一节。
求二叉树的层序遍历是原样形态，关键是每轮开始前先记下当前队列长度，
用它划出「这一层有几个节点」，否则分不了层。
按之字形顺序打印二叉树只是在偶数层把该层结果 reverse() 一下——
不要真的反着遍历，那会把左右孩子的入队顺序也搞乱。
输出二叉树的右视图取每层的最后一个节点；
它的题面给的是前序与中序两个序列，所以要先按 §3 的重建法建树再做层序，
两步都是本章现成的模板。
由遍历序列重建，§3 末尾那一节讲的就是它。 重建二叉树是「前序给根、中序切左右」的标准题， 实现上有两个要点：预先建「值 → 中序下标」的字典把每层找根降到 \(O(1)\)（总复杂度 \(O(n)\)）， 以及把递归改写成栈里存「节点 ＋ 它负责的两段区间」。 序列化二叉树是它的对偶——把树写成串再读回来。 判题只比「一个来回之后的树与原树是否同构」，中间那个串的格式不参与比较， 所以格式可以自己挑；唯一的硬要求是两个方法严格咬合。 只用前序不够：只有一个孩子时，孩子挂左还是挂右，前序序列一模一样， 必须补上空节点占位才能区分。
深度、对称与结构判定，一趟遍历就能顺手带出来。 二叉树的最大深度（同一道题在另一处题库里编号 LC 104. 二叉树的最大深度）是层序的层数， 也可以在后序里用「左右子树深度取大加一」自底向上算。 判断是不是平衡二叉树用的正是后一种写法： 每个节点回报自己的高度，顺便检查左右高度差是否超过 1， 一旦超限就沿途把「不平衡」这个信号传上去，整棵树只遍历一遍； 先算高度再逐点判断的写法是 \(O(n^2)\)。 对称的二叉树把「一棵树自身对称」转成「两个指针镜像同步走」： 一个走左孩子时另一个走右孩子。 二叉树的镜像是把这件事真做出来——逐点交换左右孩子。 合并二叉树同步遍历两棵树，一方为空就直接挂上另一方的整棵子树。
两道跟二叉搜索树有关的。 判断是不是二叉搜索树的正确判据不是「每个节点大于左孩子小于右孩子」， 那个条件太弱；正确的做法要么中序遍历后检查是否严格递增， 要么在递归中带上 \((\min, \max)\) 区间往下传。 二叉搜索树与双向链表要求原地改成有序双向链表， 本质就是中序遍历时把「上一个访问过的节点」与当前节点互相牵手， 用模板二的迭代版写，额外空间是 \(O(h)\) 的栈。
剩下两道。 判断是不是完全二叉树用层序， 但空孩子也要入队：一旦弹出过一个空节点，后面就不允许再出现非空节点。 二叉树中和为某一值的路径(一)是根到叶的路径和判定， 把「剩余目标值」随遍历一路减下去，到叶子处判零即可； 注意必须走到叶子才算数，半路凑够了不算。
另一处题库里的九道二叉树题¶
三道「在遍历里加两行」的题。 LC 226. 翻转二叉树在任意一种遍历里插一句「交换左右孩子」即可，\(O(n)\)。 LC 101. 对称二叉树要同时走两棵子树：把「左的左」对「右的右」、「左的右」对「右的左」递归下去， 判空的分支要写全三种——两侧都空为真、只有一侧空为假、值不等为假。 LC 114. 二叉树展开为链表按先序把树摊成只有右孩子的链， \(O(1)\) 额外空间的写法是自上而下：对每个有左子树的节点， 把左子树整棵接到右边，原来的右子树挂到左子树的最右节点下面，然后走到右孩子继续。
三道吃「二叉搜索树中序有序」这条性质的题。 LC 98. 验证二叉搜索树的正确判据是开区间下传： 每个节点带着一对上下界往下走，左子把上界收成当前值、右子把下界收成当前值。 只比较父子两个节点是错的——根为 \(10\)、右子为 \(15\)、而 \(15\) 的左子为 \(6\) 时， \(6\) 在根的右子树里却小于 \(10\)，父子比较看不出来。 中序遍历判是否严格递增是另一条等价的路。 LC 230. 二叉搜索树中第 K 小的元素就是中序遍历数到第 \(K\) 个， 用显式栈可以数够就停，平均只走 \(O(H + K)\) 个节点。 LC 108. 将有序数组转换为二叉搜索树反过来做：每次取区间中点当根、左右两半递归， 高度是 \(\lceil \log_2 n \rceil\)，天然平衡。
LC 105. 从前序与中序遍历序列构造二叉树。 前序的第一个是根，在中序里定位到它，左右子树的规模就定死了。 每次线性查找是 \(O(n^2)\)，先用哈希表把「中序的值 → 下标」建好之后降到 \(O(n)\)。 题面保证值互不相同，这个哈希表才建得起来；有重复值时前序加中序不足以唯一确定一棵树。
LC 543. 二叉树的直径 与本章直径那一节的做法二是同一套： 一次后序遍历，每个节点用「左深 ＋ 右深」更新答案，返回值取「较深的一侧 ＋ 1」，\(O(n)\)。 要留意题面要的是边数，而后序遍历自然算出来的是节点数，答案要减一。
LC 437. 路径总和 III：把前缀和搬到根到当前节点的这条链上。 路径必须向下但起点任意，等价于「同一条链上任取两点、其间的和为目标值」—— 正是前缀和配哈希表那一套，只不过前缀数组换成了递归栈上的一条链。 进入节点时把当前前缀和的计数加一、离开时必须减回去， 否则另一棵子树会数到不在同一条链上的前缀；\(O(n)\) 时间、\(O(H)\) 空间。
这些题的节点数上限在 \(10^4\) 到 \(10^5\) 之间。树退化成一条链时递归深度等于节点数， 而默认递归上限只有 \(10^3\) 量级，所以除了 LC108 这种自带 \(O(\log n)\) 高度保证的题， 其余都要把递归改写成显式栈的迭代式遍历。
9 本章速查¶
树的性质与存储¶
| 要点 | 结论 |
|---|---|
| 树的定义 | 连通 + 无环 |
| 三选二定理 | 连通 / 无环 / \(m=n-1\) 任意两条 ⟹ 是树 |
| ⚠️ 只判 \(m=n-1\) | 不够，必须配连通性 |
| 任意两点 | 有唯一简单路径 |
| 加一条非树边 | 恰好产生一个环 |
| 度数和 | \(2(n-1)\)，平均度数 \(< 2\) |
| 树是二分图 | 无环 ⟹ 无奇环 |
| 找根 | 题目给 / 入度为 0（BISHI96）/ 随便取 1 |
| 换根 | \(sz'[u] = n - sz[v]\) |
| 二叉树存储 | left[] + right[] 两个数组，0 表示空；❌ 别用节点类 |
| 大树存储 | CSR（\(n \ge 2\times10^5\) 必用） |
遍历与序¶
| 要点 | 结论 |
|---|---|
| 三种遍历 | 先序 根左右 / 中序 左根右 / 后序 左右根 |
| 必须迭代 | 树高上界 \(= n\)，\(n \ge 1000\) 递归必爆（BISHI96 的 \(10^5\)） |
| 先序迭代 | 栈里先压右再压左 |
| 中序迭代 | 一路向左压栈 → 弹出访问 → 转右子树 |
| 后序迭代 | 按「根右左」跑先序，最后 reverse()（最短最快） |
| 后序的三种写法 | 反转法 ✅ > 双栈法 ⚠️ > 标记元组法 ❌ |
| BST 的中序 | 是有序的 |
| 重建二叉树 | 先序+中序 ✅、后序+中序 ✅、先序+后序 ❌ |
reversed(BFS 序) = 后序 |
树上 DP 的 Python 标准姿势，无递归无栈 |
| DFS 序（先序） | 长 \(n\)；子树 = 连续区间 \([tin_u, tin_u+sz_u-1]\) |
| 括号序 | 长 \(2n\)；判祖先、树上莫队 |
| 欧拉序 | 长 \(2n-1\)；LCA → RMQ |
| 判祖先 \(O(1)\) | tin[u] <= tin[v] < tin[u] + sz[u] |
| 子树改 → 区间改 | DFS 序 + 树状数组 / 线段树 |
| 路径改 → 区间改 | 需要树链剖分（树链剖分） |
| BFS 序能做子树区间吗 | ❌ 不能，子树在 BFS 序里不连续 |
直径与重心¶
| 要点 | 结论 |
|---|---|
| 直径 | 树上最长简单路径；端点一定是叶子 |
| 两次 BFS | 任意点 → 最远点 \(a\) → 从 \(a\) 出发的最远点 \(b\) |
| ⚠️ 两次 BFS 的前提 | 边权非负；有负权必须树形 DP |
| 树形 DP 求直径 | 最长链 + 次长链；先更新答案再更新 down |
| 重心 | 删掉后最大块最小；等价于「距离和最小」；至多 2 个 |
| 重心的关键性质 | 最大子树 \(\le \lfloor n/2 \rfloor\) ⟹ 点分治深度 \(O(\log n)\) |
| 中心 | 到最远点最近；就是直径的中点。⚠️ 与重心不是一回事 |
路径长度、树上差分与 LCA 的速查条目在 LCA 与树上路径 章末。