01先把问题说具体
输出树 4(2(1,3),7) 的根、左、右遍历顺序,并在迭代代码中保持相同顺序。
02一步步得到方法
前序描述的是访问时机
来到节点先处理根,再递归左子树,最后右子树,所以树根总是首先出现。常用于复制结构、记录进入节点的路径状态;但只记录值通常不足以唯一恢复一棵任意二叉树。
递归调用本身保存尚未执行的右子树。改写为显式栈时,要主动把待办任务压入栈。由于后进先出,应先压右孩子,再压左孩子,这样左边先被弹出。
遍历与序列化有何区别
若要从前序结果恢复一般二叉树,需要保留空孩子标记,例如 [4,2,1,#,#,3,#,#,7,#,#]。没有空标记时,[1,2] 可以表示根 1 的左孩子 2,也可以表示右孩子 2。
访问时机与栈顺序对应
前序在刚进入节点时处理它,再进入左子树、右子树,因此根一定最先出现。它适合先处理父级再展开下级,例如输出目录结构或生成带空标记的树表示。
用显式栈模拟时,后压入的孩子先出栈。要让左孩子先处理,应先压右、再压左。遇到只存在一个孩子的树也应保持同样规则。
03把一个小例子完全算清楚
树 4(2(1,3),7),栈右侧为栈顶。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 弹出 4 | 输出 [4],栈 [7,2] | 右先压,左后压 |
| 弹出 2 | 输出 [4,2],栈 [7,3,1] | 保持根左右 |
| 弹出 1、3、7 | [4,2,1,3,7] | 叶子不增加任务 |
窄屏可左右滑动表格,阅读完整计算与理由。
前序结果 [4,2,1,3,7]。
04为什么这个方法成立
- 栈顶始终为递归顺序中下一棵待处理子树的根。
- 访问根后把右子树任务放在左子树任务下方,保持左先右后的安排。
- 每个节点只入栈一次,最终所有节点恰好访问一次。
05把推导翻译成代码
Python · 可独立运行的教学实现
def preorder(tree):
# tree 用 (value, left, right) 表示,空树为 None
if tree is None:
return []
stack, output = [tree], []
while stack:
value, left, right = stack.pop()
output.append(value)
if right is not None:
stack.append(right)
if left is not None:
stack.append(left)
return output逐个理解关键决定
stack.append(right)- 先保存稍后才处理的右子树。
output.append(value)- 访问发生在孩子之前,是前序与其他遍历的核心区别。
06时间、空间与实现范围
时间 O(n),栈最多 O(h) 个待处理分支,输出 O(n)。
递归和迭代只是保存待办状态的不同方式,不会自动改变遍历定义。
07改变条件,检查哪里会出错
先压左再压右
会得到根右左顺序;根据栈的后进先出倒推压栈顺序。
仅前序序列就声称能唯一还原任意二叉树
没有额外结构信息时通常不唯一;需空节点标记或在满足条件时结合中序等信息。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
根 1 只有右孩子 2,前序是什么?
需要一点提示
空左子树不输出。
查看解析与答案
[1,2]。
前序值序列能唯一确定树吗?
需要一点提示
考虑只有一个孩子的根。
查看解析与答案
一般不能;加入空节点标记,或结合满足条件的另一种遍历才能恢复。
要统计根到叶路径的前缀,何时加入当前值?
需要一点提示
在进入孩子前建立父路径。
查看解析与答案
进入节点时加入,完成子树后撤销;注意为输出路径保存快照。