二叉树遍历：四把钥匙，打开树的四种“世界视图”-平芜编程栈

二叉树遍历：四把钥匙，打开树的四种“世界视图”

想象你拿到一张藏宝图（二叉树），你可以选择：直奔主题先找宝藏（前序），按图索骥依次探索（中序），扫清障碍最后拿宝（后序），或者一层层地毯式搜索（层序）——这就是遍历，四种打开同一棵树的不同方式。

当你面对一棵枝繁叶茂的二叉树，如何系统地“拜访”每一个节点？这可不是随机漫步，而是有章可循的经典算法。遍历不仅是基础，更是理解树结构思维的关键——同样的树，不同的访问顺序，能看到完全不同的逻辑世界。

01 两大门派：深度优先 vs 广度优先

在深入了解四种具体遍历方式前，我们先从高处俯瞰，将它们归入两大思想阵营：

深度优先遍历：包括前序、中序、后序。它们的策略很像走迷宫时的**“一条路走到黑”，会优先沿着一条分支深入到底，再回溯探索其他分支。通常使用递归或栈**来实现，体现了“后进先出”的回溯思想。
广度优先遍历：即层序遍历。它的策略更像是**“水波扩散”，从起点开始，一层一层均匀地向外探索。通常使用队列**来实现，体现了“先进先出”的公平思想。

flowchart TD A[“开始遍历二叉树”] --> B{选择遍历策略}; B --> C[“深度优先搜索<br>(DFS)”]; B --> D[“广度优先搜索<br>(BFS/层序)”]; C --> E{选择节点访问顺序}; E --> F[“前序遍历<br>根 -> 左 -> 右”]; E --> G[“中序遍历<br>左 -> 根 -> 右”]; E --> H[“后序遍历<br>左 -> 右 -> 根”]; F --> I[“应用: 复制树, 前缀表达式”]; G --> J[“应用: BST升序输出, 表达式树”]; H --> K[“应用: 删除树, 计算目录大小”]; D --> L[“应用: 按层处理, 找最短路径”];

理解了这个宏观分类，我们再具体看每一种遍历如何“行走”。

02 深度优先遍历之一：前序遍历

口诀：根 -> 左 -> 右

🧭 思维过程：第一次探索的游客

想象你是一个第一次来到树形公园的游客，你的任务是每到一地，先拍地标（访问根），然后深入左边的景区，最后探索右边的景区。你对每个子景区都重复这个“拍地标->左->右”的过程。

访问上图树的顺序：A → B → D → E → C → F → G

💡 为什么这个顺序有用？

因为你是从根节点开始，完整地复制了树的拓扑结构。你知道第一个一定是根，然后是左子树的全部，再是右子树的全部。这非常符合人类“从上到下、从主干到枝叶”的认知习惯。

🛠️ 核心应用场景

复制一棵树：你必须先创建根节点，才能挂接它的左右子树。前序访问是唯一自然的选择。
获取表达式的前缀表示（波兰式）：例如，表达式树* ( + 2 3 ) 4，前序遍历会得到* + 2 3 4，无需括号就能无歧义地运算。
序列化树结构：将树转化为字符串或数组存储时，前序顺序很容易被还原。

📝 代码实现（Python递归版）

defpreorder_traversal(root):result=[]defdfs(node):ifnotnode:returnresult.append(node.val)# 1. 访问根dfs(node.left)# 2. 遍历左dfs(node.right)# 3. 遍历右dfs(root)returnresult

递归三行，严格对应“根左右”的口诀。

03 深度优先遍历之二：中序遍历

口诀：左 -> 根 -> 右

🧭 思维过程：认真的研究者

这次你像一个严谨的研究员，对待每个局部，你坚持“先彻底搞清楚左边的所有细节（左），再总结当前节点的核心结论（根），最后再去研究右边的所有细节（右）”。

访问上图树的顺序：D → B → E → A → F → C → G

💡 为什么这个顺序特殊？

对于一颗二叉搜索树，中序遍历有一个魔法般的性质：它会以升序（或降序）输出所有值。因为BST的定义是：左子 < 根 < 右子。中序遍历的“左-根-右”顺序，完美地将这个有序性展现了出来。

🛠️ 核心应用场景

二叉搜索树的升序/降序输出：这是中序遍历的“杀手级应用”，用于获取有序数据。
表达式树的中缀输出：对于(2 + 3) * 4这样的表达式树，中序遍历会得到2 + 3 * 4（可能需要加括号）。
恢复BST的结构：结合前序或后序遍历结果，可以唯一确定一棵BST。

📝 代码实现（Python递归版）

definorder_traversal(root):result=[]defdfs(node):ifnotnode:returndfs(node.left)# 1. 遍历左result.append(node.val)# 2. 访问根dfs(node.right)# 3. 遍历右dfs(root)returnresult

仅仅是访问根节点的时机，从最前挪到了中间。

04 深度优先遍历之三：后序遍历

口诀：左 -> 右 -> 根

🧭 思维过程：负责的清理者

现在你扮演一个负责的管家，在处理任何一个区域时，你都坚持“先搞定左边所有子区域的问题（左），再搞定右边所有子区域的问题（右），最后才处理当前区域自己的事情（根）”。

访问上图树的顺序：D → E → B → F → G → C → A

💡 为什么这个顺序安全？

因为它是自底向上的。在访问一个节点时，它的所有后代都已经被访问过了。这就像拆房子，你必须先拆除所有门窗和内部结构（子树），最后才能安全地拆除主梁（根）。

🛠️ 核心应用场景

删除一棵树：你必须先递归地删除左右子树，才能释放当前根节点的内存。这是最安全的顺序。
计算目录大小：在文件系统树中，一个目录的总大小等于其下所有子目录和文件的大小之和。必须算完所有子项，才能得到当前目录的总和。
获取表达式的后缀表示（逆波兰式）：例如(2 3 +) 4 *，后序遍历得到2 3 + 4 *，这种表示便于计算机用栈来计算。

📝 代码实现（Python递归版）

defpostorder_traversal(root):result=[]defdfs(node):ifnotnode:returndfs(node.left)# 1. 遍历左dfs(node.right)# 2. 遍历右result.append(node.val)# 3. 访问根dfs(root)returnresult

访问根节点的操作，被坚定地放在了最后。

05 广度优先遍历：层序遍历

口诀：按层，从左到右

🧭 思维过程：高效的指挥官

你不再深入单条分支，而是像指挥官一样，逐层检阅部队。从根节点（第一层）开始，访问完同一层的所有节点后，再一起进入下一层。

访问上图树的顺序：A → B → C → D → E → F → G

💡 为什么需要队列？

层序遍历无法用简单的递归描述，因为它需要“齐头并进”。队列完美解决了这个问题：

将根节点放入队列。
只要队列不空，就取出队首节点访问，然后立即将其左右孩子（如果存在）依次放入队尾。
这样，上一层节点访问完毕时，下一层节点已经在队列中排好队了。

🛠️ 核心应用场景

按层级处理数据：打印公司组织结构图、多级标题。
寻找最短路径：在树（或图）中，层序遍历首次到达目标节点的路径，一定是边数最少的路径。
判断完全二叉树：结合层序遍历，可以高效检查树的紧凑性。

📝 代码实现（Python迭代-队列版）

fromcollectionsimportdequedeflevelorder_traversal(root):ifnotroot:return[]result=[]queue=deque([root])# 队列初始化，放入根节点whilequeue:node=queue.popleft()# 取出当前层的一个节点result.append(node.val)# 将下一层的节点放入队列ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnresult

队列是层序遍历的灵魂，它保证了“先进先出”的层级顺序。

06 终极对比与速记指南

让我们用一棵具体的树，一次性输出四种遍历的结果，并总结其核心逻辑：

示例树：

A / \ B C / \ / \ D E F G

遍历方式	访问顺序	核心口诀	思维类比	核心数据结构
前序	A, B, D, E, C, F, G	根左右	“探险家”：先标记，再探索	递归栈/显式栈
中序	D, B, E, A, F, C, G	左根右	“研究者”：先细节，后结论	递归栈/显式栈
后序	D, E, B, F, G, C, A	左右根	“管家”：先子问题，后自己	递归栈/显式栈
层序	A, B, C, D, E, F, G	按层扫	“指挥官”：逐层平推	队列