树的遍历不只是一组需要背诵的术语。遍历把分支结构转化成线性序列；重建则反过来追问：序列究竟保留了多少原有结构？这两个任务都由同一个递归分解支配，也就是根节点、左子树、右子树。
本节先精确定义三种深度优先遍历，再证明递归过程正确，最后研究如何由先序加中序，或后序加中序重建二叉树。所有“唯一重建”的结论都有一个不可省略的前提：各节点的键值互不相同。
动机
假设程序遍历一棵树后，只保存节点键值的序列。另一个程序以后能否恢复完全相同的树？答案取决于遍历顺序揭示了什么。
- 先序遍历会在后代之前揭示每棵非空子树的根节点。
- 后序遍历会在后代之后揭示这个根节点。
- 中序遍历把整棵左子树放在根节点之前，把整棵右子树放在根节点之后。
其中任何一项通常都不足以独立还原结构。有效的组合是：先序或后序负责指出根节点，中序负责指出左右子树的分界。因此，重建不是一套零散技巧，而是重复维护同一个递归不变量。
定义
定义
二叉树与递归子树结构
二叉树或者是空树，或者由一个根节点及一对有顺序的二叉树组成；两者分别称为左子树与右子树，任何一边都可以是空树。
左右顺序是结构的一部分。交换左、右子节点后，通常会得到另一棵二叉树。
非空树的根节点没有父节点。直接位于某节点下一层的是它的子节点；沿子节点链接反复向下可以到达的节点是后代，反方向则是祖先。没有子节点的是叶节点，至少有一个子节点的是内部节点。以某节点为根的子树包含该节点及其全部后代。
以下用 h 表示最长根到叶路径上的节点数，因此单节点树的高度为 1。这个约定使后面的递归调用栈界限没有歧义。
定义
先序、中序与后序遍历
对于根节点为 R、左子树为 L、右子树为 T 的非空二叉树：
- 先序（preorder）是
R，再遍历L，最后遍历T； - 中序（inorder）是先遍历
L，再到R，最后遍历T； - 后序（postorder）是先遍历
L，再遍历T，最后才到R。
空树的遍历结果是空序列。
定义可以直接写成递归伪代码：
Preorder(node): Inorder(node):
if node is null: return if node is null: return
visit(node) Inorder(node.left)
Preorder(node.left) visit(node)
Preorder(node.right) Inorder(node.right)
Postorder(node):
if node is null: return
Postorder(node.left)
Postorder(node.right)
visit(node)
三个过程只改变 visit 的位置，却会改变每段子树序列的开头或结尾所揭示的信息。中序遍历本身不是排序；只有当树另外满足二叉搜索树不变量时，中序键值才会递增。这个不变量将在下一篇笔记中处理。
还要精确区分各序列保留的信息。在边界已经确定的子树内，先序首项是根，后序末项是根；如果根已经确定，那么中序中根之前的项全部属于左子树，之后的项全部属于右子树。但是中序本身不会指出哪一项是根，而本节采用的三种序列也不记录空子节点标记。这正好说明重建定理的两面：能识别根的顺序与中序相互补充；缺少分界或根的选择时，多种树形就可能共享同一个序列。
“边界已经确定”尤其重要。只有在递归算法已经确立区间后，一段连续遍历序列才代表一棵子树；不能随意从完整序列截取一段，就假定它一定是一棵子树。
定理 / 命题
定理
递归遍历不变量
三种过程中的任何一个在某棵子树上执行时，都会恰好一次遍历该子树的每个节点，不会访问子树以外的节点，并按照相应递归定义输出节点。
定理
由中序及能够识别根节点的顺序唯一重建
假设所有节点键值互异。如果两个相容序列分别是一棵二叉树的先序和中序遍历，它们唯一确定一棵有左右顺序的二叉树。后序配合中序也有相同结论。
定理
单一中序序列并不充分
即使键值互异，只凭中序遍历通常也不能确定根节点、父子关系或二叉树形状。
“相容”不是多余的限定。两个输入必须长度相同、键值集合相同，而且每次递归选出的根都必须位于当前中序区间内；否则两个序列并不描述同一棵树。
证明思路
遍历正确性可以对当前子树的节点数做归纳。空树调用立即返回，命题成立。对于非空子树，两次递归调用分别作用于更小的左、右子树，因此根据归纳假设已经正确。过程只访问根一次，并把它放在两段正确结果之前、之间或之后，所以每个节点恰好出现一次，顺序也符合定义。
考虑由先序和中序重建，令 P、I 表示当前两段序列。P 的第一个键必为根 r。由于键值互异，r 在 I 中只有一个位置；它前面的项全部属于左子树，后面的项全部属于右子树。两边长度因而把 P 的剩余部分唯一切成左右两段。对两段重复同一论证，对长度做归纳，就同时得到相容输入的存在性和唯一性。
如果使用后序，当前后序段的最后一个键就是根。中序仍然固定左右大小，而后序段的形式是“左、右、根”，所以两段子树输入也被唯一确定。
键值互异不是装饰性条件。如果有重复值，根值可能在中序中出现多次，“在中序中找根”就不能选择唯一分界。此时必须增加节点身份，例如给每次出现添加独立标签，或者明确规定重复值策略；原始重复值本身不足以套用上述定理。
下面的反例证明单一中序并不充分。两棵树的中序都是 (B, A, C)：
A C
/ \ /
B C A
/
B
序列只固定从左到右的顺序，没有指出哪个键是根。同样，先序 (A, B) 和后序 (B, A) 既可以描述 B 是左子节点，也可以描述它是右子节点。因此，如果没有额外结构条件，先序加后序仍不足以唯一重建任意二叉树。
例题
例题
在同一棵树上追踪三种顺序
考虑课程遍历例子中的树：
A
/ \
B C
/ / \
D E F
\ / \
G H J
在每棵子树上分别应用递归规则，可以得到：
- 先序：
A, B, D, C, E, G, F, H, J； - 中序：
D, B, A, E, G, C, H, F, J； - 后序：
D, B, G, E, H, J, F, C, A。
例如，以 C 为根的子树在三种顺序中分别贡献 C,E,G,F,H,J、E,G,C,H,F,J 和 G,E,H,J,F,C。先把它看成一个较小的完整问题，可以避免把节点误放到相邻子树。
例题
由先序与中序重建
使用上面的先序与中序。先序首项是 A，所以根为 A。中序可以写成
D,B | A | E,G,C,H,F,J，
左子树有两个节点，因此先序中紧跟 A 的 B,D 构成左子树，剩下的 C,E,G,F,H,J 构成右子树。
左段以 B 为根，而 D | B 表示 D 是它的左子节点。右段以 C 为根，E,G | C | H,F,J 固定一棵两节点左子树和一棵三节点右子树。继续分割，得到 E 的右子节点 G，以及 F 的左、右子节点 H、J。
使用闭区间索引和“键值到中序位置”索引表，核心过程如下：
BuildPre(preLo, preHi, inLo, inHi):
if preLo > preHi or inLo > inHi:
require preLo > preHi and inLo > inHi
return null
rootKey = preorder[preLo]
k = inorderPosition[rootKey]
require inLo <= k <= inHi
leftSize = k - inLo
node = new Node(rootKey)
node.left = BuildPre(preLo + 1, preLo + leftSize,
inLo, k - 1)
node.right = BuildPre(preLo + leftSize + 1, preHi,
k + 1, inHi)
return node
例题
由后序与中序重建
改用后序 D,B,G,E,H,J,F,C,A 以及同一中序。后序末项 A 是根；中序仍然给出左边两个、右边六个节点，因此后序分成
D,B | G,E,H,J,F,C | A。
右段末项是 C；它的中序分割为 E,G | C | H,F,J，所以对应的后序子段为 G,E 和 H,J,F。由此得到 E 的右子节点 G，以及 F 的两个子节点 H、J。
BuildPost(postLo, postHi, inLo, inHi):
if postLo > postHi or inLo > inHi:
require postLo > postHi and inLo > inHi
return null
rootKey = postorder[postHi]
k = inorderPosition[rootKey]
require inLo <= k <= inHi
leftSize = k - inLo
node = new Node(rootKey)
node.left = BuildPost(postLo, postLo + leftSize - 1,
inLo, k - 1)
node.right = BuildPost(postLo + leftSize, postHi - 1,
k + 1, inHi)
return node
这个区间版本先构造哪一边都可以。如果另一种实现用同一个游标从后序末端逐项读取，就必须先构造右子树，因为反向读取的顺序是“根、右、左”。
例题
先识别不相容输入，不要虚构树
如果先序是 (A, B, C)，中序却是 (B, A, D)，两者的键值集合不同，所以不存在同时具有这两个遍历结果的树。另一种错误是：当前先序根虽然出现在完整中序中，却落在当前中序区间之外；这表示它与更早的父子分割冲突。稳健的实现应当拒绝输入，而不是默默返回残缺的树。
复杂度
假设 visit 只做常数时间的局部工作，每种遍历都恰好处理 n 个节点一次，因此时间为 Theta(n)。递归调用栈占用 O(h) 空间：当树高关于 n 是对数级时为 O(log n)，完全偏斜的树则是 O(n)。如果需要保存输出序列，还要使用 Theta(n) 空间。
重建时，如果每次都线性扫描当前中序段寻找根，偏斜输入可使总时间达到 Theta(n^2)。更好的方法是先检查键值集合，用 Theta(n) 时间建立每个互异键值到中序索引的表，并传递索引边界而不是复制子数组。假设查表为常数时间，每个节点只创建一次，总时间就是 Theta(n)。索引表占用 Theta(n) 辅助空间，递归另占 O(h)；输出的树本身必然占用 Theta(n)。
常见错误
常见错误
误以为任何二叉树的中序都有排序效果
中序只表示“左、根、右”。只有另一个不变量，例如二叉搜索树不变量，才能保证键值递增。
常见错误
用先序或后序猜测左右分界
先序、后序能够指出子树根；左右各有多少节点则必须由中序确定。缺少这个分界时，子树边界通常有歧义。
常见错误
忘记键值互异的前提
同一个值出现多次时，单一“值到索引”表不能证明根只有一个位置；必须标记每次出现或者另外制定重复值策略。
常见错误
把平方时间隐藏在递归中
每层扫描中序或复制切片，都可能让看似简单的过程变成平方时间。应预先建立位置表并传递边界。
常见错误
反向游标先构造了错误的一边
使用共享游标从后序末端读取时，应先右后左。区间版本已经明确计算两个子段，没有这项先后依赖。
总结
- 三种遍历只改变根节点的处理时刻，却分别揭示不同的结构信息。
- 每次递归调用只负责一棵子树，这正是遍历正确性的不变量。
- 键值互异时，先序加中序或后序加中序可以唯一确定有左右顺序的二叉树。
- 只用中序，以及对于任意二叉树只用先序加后序，都可能产生歧义。
- 位置索引表加区间边界，可以把可能的
Theta(n^2)重建降到Theta(n)。
练习
思考检查
1. 一棵树以 M 为根；左子节点 H 有右子节点 K；右子节点 T 有左子节点 P。写出先序、中序与后序。
先在每棵子树上应用同一个递归模板，再合并结果。
思考检查
2. 已知先序为 (M,H,K,T,P)，中序为 (H,K,M,P,T)，找出根以及两棵子树各自的两个序列段。
利用根在中序中的位置以及由此得到的左子树大小。
思考检查
3. 已知后序为 (K,H,P,T,M)，中序同上，找出根以及左右后序子段。
根在后序末端，而中序仍然提供两边的大小。
思考检查
4. 解释先序 (A,B) 与后序 (B,A) 为什么不能判断 B 是左子节点还是右子节点。
构造两棵具有相同序列的有序二叉树。
思考检查
5. 为什么每层扫描中序可能需要平方时间？哪两项实现选择可以恢复线性时间？
先考虑偏斜树，再分别处理寻找根与复制子数组的成本。
解答
解答 · 1. 遍历追踪
先序为 M,H,K,T,P；中序为 H,K,M,P,T；后序为 K,H,P,T,M。对于 H，空左子树没有输出；K 在先序中紧跟 H，但在另外两种遍历中要先完成相应子树才返回 M。
解答 · 2. 先序与中序分割
根是 M。中序分成 H,K | M | P,T，左右各有两个节点；读取先序的根项 M 后，剩余先序段相应分成 H,K | T,P。两组递归输入分别是先序 (H,K) 配中序 (H,K)，以及先序 (T,P) 配中序 (P,T)。
解答 · 3. 后序与中序分割
末项 M 是根。根据中序大小，可以把前面的后序键分成 K,H | P,T | M。因此左后序 (K,H) 配左中序 (H,K)；右后序 (P,T) 配右中序 (P,T)。
解答 · 4. 歧义
第一棵树以 A 为根、B 为左子节点；第二棵以 A 为根、B 为右子节点。两者的先序都是先 A 后 B，后序都是先 B 后 A。序列没有记录哪一边为空，所以不能分辨形状。
解答 · 5. 修正复杂度
偏斜树上的扫描长度可以依次为 n,n-1,...,1，总和是 Theta(n^2)。先建立“键值到中序索引”表，使每次寻找根为常数时间；再传递整数边界，避免复制子数组。在查表假设下，每个节点只处理一次，总时间为 Theta(n)。