信息技术大学
二叉树遍历
数据结构与算法·面试高频 · 第 2 章 树与图
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
二叉树遍历
数据结构与算法·面试高频 · 第 2 章 树与图
前中后序迭代写法
递归一行，迭代靠栈：前序直白，中序一路向左，后序用「前序反转」取巧。
前序迭代
弹出即访问，先压右孩子再压左孩子
中序迭代
一路向左压栈，到底弹出访问再转向右子树
后序取巧
按根右左遍历，结果整体反转即左右根
层序遍历变体
队列逐层推进：记下每层长度，一层一层出，变体只是换个记录方式。
分层
每轮先记队列长度，恰好消费完一层
锯齿形
奇偶层交替反转，或用双端队列
右视图
每层最后一个出队的节点进结果
路径总和系列
从根到叶的路径账：递归带减法，走到叶子核对余额，存路径要回溯。
判定存在
目标值逐层递减，叶节点判断是否归零
收集路径
路径入列表递归，返回前移除回溯
子树判断
判断 t 是否 s 的子树：对 s 每个节点做一次「同根判等」，或串化后找子串。
双重递归
每个节点尝试 isSame，任一命中即真
同构判等
值与左右子树同时相等才算相同
串化技巧
前序串化带空位标记，t 的串是 s 的子串
本节要点
- ✓迭代靠栈：中序一路向左
- ✓层序靠队列：长度定层界
- ✓路径总和：递减到叶子对账
- ✓子树判断：双重递归或串化找子串
延伸主题：手写中序迭代刷右视图
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1后序迭代为什么可以用「根右左」加反转取巧？
参考答案后序是左右根，根右左恰是其镜像；栈天然逆序，按根-右-左的顺序压栈访问得到根右左，整体反转即左右根。不优雅但考场救命。
2层序遍历的「先记长度」技巧为什么不可省？
参考答案队列里同时存在两层节点，不按层截断就无法区分边界；先记当前长度再出队，保证本轮恰好消费完一层——分层、锯齿、右视图全依赖它。
3子树判断的双重递归为什么是 O(n×m)？串化法优势在哪？
参考答案s 的每个节点都可能发起一次对 t 的同构判等 O(m)；串化后变成纯字符串子串查找，KMP 或内建函数 O(n+m) 一次搞定，用空间换时间。