遍历与层序视角解题框架
本节目标
从节点访问时机出发，用显式栈和按层队列组织二叉树遍历。
第七章公共示例树
根 1，左右孩子 2、3，节点 2 的左右孩子为 4、5。
1
/ \
2 3
/ \
4 5
同一棵树可以按深度优先的访问时机读取，也可以按广度优先的一层一层读取；首先要确定答案要求的是哪一种顺序。
识别信号
- 题目直接要求前序、中序或后序序列；
- 需要逐层输出、统计层数，或从每层取一个节点；
- 节点处理的时机在进入节点、两个子树之间，或离开节点时不同；
- 结果的顺序由栈或队列中的待处理工作决定。
问题模型与核心不变量
公共树的前序为 1, 2, 4, 5, 3；按层读取时，队列边界依次对应 [1]、[2, 3]、[4, 5]。
前序在进入节点时访问，因此示例树得到 1, 2, 4, 5, 3；中序在左右子树之间访问，得到 4, 2, 5, 1, 3；后序在离开节点时访问，得到 4, 5, 2, 3, 1。
递归调用栈和显式栈保存的都是尚未完成的工作。前序迭代中，先压右孩子再压左孩子，栈顶才会先给出左子树。层序遍历则使用队列；进入一层时记录的队列长度，就是这一层固定的边界，随后新入队的孩子只能属于下一层。
通用模板
前序：根入栈；弹出并访问；先压右、再压左
中序：持续压左链；弹出并访问；转向右孩子
后序：按根—右—左收集；整体反转
层序：根入队
while 队列非空：
levelSize = 当前队列长度
恰好弹出 levelSize 个节点并按需收集
将它们的孩子加入队尾
模板变体
- 前序可直接记录根，也可在入栈时保存额外路径状态。
- 中序的“左链全部入栈”是 BST 第 K 小等问题的基础。
- 后序的根—右—左反转写法避免为每个节点维护额外访问标记。
- 层序中可收集完整的
level，也可以只保留第一个、最后一个或层宽等统计量。
母题序列
按必学顺序练习：
- 二叉树的前序遍历：理解为何右孩子要先入栈。
- 二叉树的中序遍历：用指针和栈持续处理左链。
- 二叉树的后序遍历：从根—右—左的收集顺序反转。
- 二叉树的层序遍历：用固定队列长度划分层边界。
- 二叉树的右视图：从每层的最后一个节点提取视图。
常见误区
- 前序把左孩子先压栈，导致右子树提前输出。
- 中序弹栈后忘记转到右孩子，或只压入一个左孩子。
- 后序直接使用根—右—左结果而没有反转。
- 层序循环条件使用不断变化的
queue.size()，让下一层节点混入当前层。 - 把 DFS、BFS 当作固定题型，而不是按输出顺序选择的遍历策略。
迁移方向
当题目从“输出所有节点”变成“在每层挑选信息”时，保留层序模板并改变收集动作即可。需要子树向父节点返回高度、平衡性等信息时，则转入子树信息与递归判断的返回值模型。