树的遍历
01 / 一句话本质
任何树的遍历算法都会恰好访问每个节点一次 —— 唯一变化的,是"访问"发生在对子节点递归下降的哪一刻。
题目按指定顺序遍历一棵二叉树二叉树[1, 2, 3, 4, 5, ·, 6]遍历前序
输出—— 暂无 ——
深度优先 —— 前序在向子节点递归之前访问节点。
步
0 / 7
正在访问
—
已访问
0 / 6
遍历
前序
0 / 7
02 / 模式骨架
# 深度优先 —— 三种变体只是"访问"放在不同位置traverse(node):if node is null: returnvisit(node) // 前序traverse(node.left)visit(node) // 中序traverse(node.right)visit(node) // 后序# 广度优先 —— 迭代,基于队列level_order(root):q ← [root]while q not empty:node ← q.dequeue(); visit(node)enqueue node.left, node.right
03 / 什么时候用这个模式
"BST 的中序"
二叉搜索树的有序输出来自中序 —— 这是 BST 的性质, 并不是中序遍历本身的一般性质。
"逐层"
需要按行处理整棵树 —— 节点深度、锯齿形输出、"找树的右视图"等等。 基于队列的层序正是这件工具。
"自底向上 / 先子后父"
只有先知道子节点的答案,才能算出当前节点的答案 —— 子树和、高度、路径等。后序能保证子节点先被访问。
"序列化 / 克隆"
把一棵树写成字符串,或是逐节点复制。常用前序外加显式的 null 标记 —— 这样能无歧义地刻画结构。
04 / 常见坑
i.
该用后序时用了中序。
任何需要根据子节点答案推父节点答案的事情 —— 子树和、高度、直径 —— 都必须在父节点之前访问子节点。这就是后序。 中序会让部分子节点访问得太晚。
ii.
漏掉判空。
递归遍历的第一行就是
if node is null: return。 漏掉它,就会在每个叶子缺失的子节点处解引用 null。 动画把这点显式呈现 —— 空子树根本不渲染。iii.
把调用栈当成输出顺序。
递归天然的调用栈并不是访问的顺序。一个节点会在自己前序访问之前就压入栈, 直到后序访问之后才弹出 —— 这是同一节点的三个不同"时刻"。
05 / 去 LeetCode 上练习
四道题。前三道是三种典型的 DFS 顺序。第四道把你带到 BFS, 是层序大放异彩的地方。