二叉树遍历
树遍历按规定顺序访问每个节点一次。先序、中序和后序使用相同的递归路线：走完左子树，返回，再走右子树。差别只有 visit(node) 的位置：两个递归调用之前、之间或之后。移动这一行，输出顺序就会改变，下降与返回路线不变。
遍历需要 O(n) 时间，递归辅助空间为 O(h)，h 是树高。不必把根—左—右、左—根—右、左—右—根当成三个互不相关的算法；它们是同一次行走中的三个记录时机。
相同路线，不同记录位置
visit(node) 可以是打印、收集或累加。递归骨架如下：
def traverse(node):
if node is None:
return
# visit(node) <- 先序放在这里
traverse(node.left)
# visit(node) <- 中序放在这里
traverse(node.right)
# visit(node) <- 后序放在这里
两个 traverse(...) 调用始终先左后右，直到空孩子 None 触发基例返回。先序一进入节点就记录，中序等待左子树结束再记录，后序等待两棵子树都结束。
每次调用孩子都会在父调用之上增加一帧。父调用暂停等待，但仍留在栈中。因此中序和后序可以在孩子之后记录父节点：孩子先执行完，父调用才继续运行到 visit。
节点使用字母 A、B、C 等标签，避免把普通二叉树误当成二叉搜索树。中序有序是 BST 的性质，任意二叉树并不保证。
二叉树遍历逐步演示
默认对偏斜程度不一的七节点树做先序遍历，与树基础课程使用同一棵树：
A
/ \
B C
/ \ /
D E F
/
G
关系为 A → B, C、B → D, E、C → F、E → G。每层都先记录，再递归左、右孩子。
- 调用 A，栈中一帧。记录 A，输出
A，递归左侧。 - 调用 B，栈中两帧。记录 B，输出
A B，递归左侧。 - 调用 D，栈中三帧。记录 D，输出
A B D。D 的两个孩子都是None，调用后立即返回；D 随后返回 B。 - B 的左侧结束，调用右孩子 E，栈恢复为三帧。记录 E，输出
A B D E，递归左侧。 - 调用 G，栈中四个非空节点帧，达到本树的显示峰值。记录 G，输出
A B D E G。G 的空孩子返回，随后 G、E、B 依次返回，回到 A。 - A 的左子树完成，调用右孩子 C，栈中两帧。记录 C，输出
A B D E G C，递归左侧。 - 调用 F，栈中三帧。记录 F，输出
A B D E G C F。F、C、A 依次结束，栈清空。
先序结果为 A B D E G C F，根 A 最先出现。面板最多显示四帧 A, B, E, G，等于树高 3 加一。空孩子的基例调用立即返回，不计入面板的非空节点帧。
在同一路线上改变记录时机
中序把记录放在两次调用之间，得到 D B G E A F C。每个节点先等左子树结束，记录自身，再处理右子树。A 位于左子树结果和右子树结果之间，并不要求是输出的正中位置。
后序在两次调用之后记录，得到 D G E B F C A。父节点都在孩子之后，根 A 最后出现。
| 顺序 | 记录位置 | 输出 |
|---|---|---|
| 先序 | 两次调用之前 | A B D E G C F |
| 中序 | 两次调用之间 | D B G E A F C |
| 后序 | 两次调用之后 | D G E B F C A |
七个非空节点的调用与返回顺序相同，变化的只有每个字母被记录的时刻。先序适合自顶向下复制或序列化树；中序在 BST 上按序输出键；后序适合先处理孩子再处理父节点，例如释放树或计算表达式树的运算结果。
为什么要观察栈深度
| 情况 | 时间 | 空间 |
|---|---|---|
| 平衡树 | O(n) | O(log n) |
| 偏斜树（单孩子链） | O(n) | O(n) |
每个节点处理常数次，时间复杂度为 O(n)。空间取决于尚未结束的调用数，即当前路径的长度。平衡树高度约为 log₂ n；单孩子链上，非空节点帧可达 n。偏斜树预设会显示全部七帧。
辅助空间为 O(h)，从平衡树的 O(log n) 增至链的 O(n)。链足够深时会导致栈溢出。处理不可信输入时可用显式栈；Morris 遍历则利用指针临时线索减少辅助栈。这也是平衡树需要限制高度的原因之一。若把收集结果的数组计入空间，还需 O(n) 输出存储。
边界情况
- 空树：
traverse(None)立即返回，所有顺序的输出都为空。 - 单节点：只有根，三种顺序都输出它，面板只有一个非空节点帧。
- 只有一个孩子：缺失侧仍会调用
traverse(None)并立即返回。默认树的 C、E 都只有左孩子，不会因此跳错记录时机。 - 叶子：两个空孩子都立即返回，递归在此转向。
- 退化成链：三种顺序仍正确，但栈深为 n，大输入宜改用迭代遍历。
常见错误
- 把三种顺序当成三个算法，忽略它们只改变
visit的位置。 - 认为根总是最先输出。先序根在前，中序根在两棵子树之间，后序根在最后；空子树也会影响中序中根的具体位置。
- 漏掉
if node is None: return，访问空孩子的字段会报错。空孩子不应被记录。 - 认为中序天然有序。只有满足 BST 排序不变量时才成立；普通树中序只是
D B G E A F C。 - 忽略深树的栈成本，直到递归溢出才处理。可用显式栈或其他迭代方法。