二叉树核心算法：彻底搞懂 BFS 与 DFS 的选择、实现与优化

在处理二叉树或图相关的算法问题时，我们面临的第一个挑战往往不是如何编写代码，而是如何选择正确的遍历策略。广度优先搜索 (BFS) 和 深度优先搜索 (DFS) 是两种最基础、最核心的遍历思维方式。它们就像是我们在探索一个错综复杂的迷宫时，选择的两种截然不同的路径：一种是像水波纹一样层层向外扩散（BFS），另一种则是选定一条路走到黑，撞墙后再回头（DFS）。

在这篇文章中，我们将深入探讨这两种算法在二叉树中的应用。你不仅会学到它们的基础定义，还会看到完整的代码实现，以及作为一名开发者，我们在实际工程中如何根据性能特征和业务场景来做出最佳选择。

树的遍历：两种截然不同的世界观

在开始之前，让我们先明确一下二叉树遍历的两种主要方式。想象一下，你正站在一棵树的根部，面前是分叉的枝干：

• 广度优先遍历：也叫层序遍历。这是最符合直觉的“扫描”方式。我们不追求深度，而是要把当前这一层的所有节点都看完，再去看下一层。就像阅读文字一样，从左到右，从上到下。
• 深度优先遍历 (DFS)：这是一种“执着的”探索方式。选定一个分支后，我们会一路深入，直到走不动为止，然后回溯到上一个路口，尝试另一条路。

深度优先遍历根据根节点的访问时机，又细分为：

* 前序遍历 (Preorder)：根 -> 左 -> 右

* 中序遍历 (Inorder)：左 -> 根 -> 右

* 后序遍历 (Postorder)：左 -> 右 -> 根

让我们先从视觉上感受一下这两种策略的区别。

!BFS vs DFS 对比.png)

图：二叉树 BFS 与 DFS 对比

什么是广度优先搜索 (BFS)？

广度优先搜索 (BFS) 是一种“地毯式”的搜索策略。在二叉树的语境下，它意味着我们在进入下一层（深度 +1）之前，必须先访问完当前层级的所有节点。这也正是为什么它被称为层序遍历 的原因。

BFS 树遍历是如何工作的？

为了实现这种“逐层扫描”的效果，我们不能仅仅依靠递归或者简单的函数调用栈，我们需要一个更强大的数据结构来协助我们——队列。

队列遵循 FIFO (First In, First Out，先进先出) 的原则，这完美契合了 BFS 的逻辑：先发现的节点先被访问，先处理完的节点先将其子节点加入待处理列表。

让我们来看看具体的执行步骤：

• 初始化：我们将根节点放入一个队列。
• 循环判断：只要队列不为空，就继续循环。
• 节点出队：从队列的头部取出一个节点，并对其进行访问（例如打印值或处理逻辑）。
• 子节点入队：检查该节点是否有左子节点和右子节点。如果有，按顺序（通常先左后右）将它们加入队列尾部。
• 重复：回到步骤 2，直到队列完全为空。

#### BFS 代码实现示例 (Python)

作为开发者，我们直接看代码会更容易理解。下面是一个使用 Python 实现的层序遍历示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    # 如果根节点为空，直接返回空列表
    if not root:
        return []
    
    # 结果列表，用于存储每一层的节点值
    result = []
    # 初始化队列，将根节点入队
    queue = [root]
    
    while queue:
        # 获取当前层的节点数量，这对于分层打印非常重要
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            # 出队操作：取出队首元素
            node = queue.pop(0)
            current_level.append(node.val)
            
            # 将左子节点入队
            if node.left:
                queue.append(node.left)
            # 将右子节点入队
            if node.right:
                queue.append(node.right)
        
        # 将当前层的结果加入总结果中
        result.append(current_level)
    
    return result

代码解析：

你可能注意到了 INLINECODEb48e1c96 这一行。这是一个非常实用的优化技巧。因为我们在循环过程中会不断地向队列添加新的一层节点，如果没有这个变量来锁定当前层的长度，INLINECODEe56cb2a4 循环可能会无限延伸，导致逻辑混乱。通过记录初始长度，我们确保了每次内层循环只处理当前层的节点。

什么是深度优先搜索 (DFS)？

与 BFS 的“横向扩展”不同，深度优先搜索 (DFS) 选择了一条“纵向深入”的道路。这种策略利用回溯 的思想：我们不断向深处挖掘，直到无路可走，然后退回到上一个分叉口，尝试另一条路。

DFS 的三种主要形式

根据我们何时访问（处理）根节点，DFS 分为三种方式。这不仅是顺序的变化，在实际解题中（如二叉树的序列化与反序列化）有着不同的妙用。

#### 1. 前序遍历

顺序： 根节点 -> 左子树 -> 右子树
直觉理解： 这就像是我们要给这棵树画一个“轮廓线”。我们刚到一个节点就先处理它，然后再去管它的孩子们。这在复制树的结构时非常有用。
代码示例 (递归)：

def preorder_traversal(root):
    if not root:
        return []
    
    # 这是一个经典的递归思路：
    # 1. 处理当前节点 (根)
    # 2. 递归处理左子树
    # 3. 递归处理右子树
    
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)

#### 2. 中序遍历

顺序： 左子树 -> 根节点 -> 右子树
直觉理解： 在二叉搜索树 (BST) 中，中序遍历会按照数值从小到大的顺序输出节点。这是 BST 最核心的特性之一。如果你需要对树中的数据进行排序，中序遍历是你的不二之选。
代码示例 (迭代法 – 使用栈)：

虽然递归很简洁，但作为追求性能的开发者，有时我们需要用栈 来模拟递归，以避免递归过深导致的栈溢出。

def inorder_traversal_iterative(root):
    if not root:
        return []
    
    stack = []
    result = []
    current = root
    
    # 当栈不为空或者当前节点不为空时，继续遍历
    while stack or current:
        # 阶段 1: 不断向左下走，将沿途节点压入栈
        # 这是为了找到最左边的节点
        if current:
            stack.append(current)
            current = current.left
        else:
            # 阶段 2: 左边没路了，弹出栈顶元素（父节点）
            current = stack.pop()
            result.append(current.val) # 处理根节点
            
            # 阶段 3: 转向右子树
            current = current.right
    
    return result

#### 3. 后序遍历

顺序： 左子树 -> 右子树 -> 根节点
直觉理解： 这是一种“自底向上”的处理方式。我们要先保证孩子们都被处理完了，才回过头来处理父节点。这在删除树（必须先删子节点再删父节点）或者计算某个目录及其子目录的总大小时非常关键。

BFS 和 DFS 的深度对比

了解了原理和代码后，让我们在实际应用的层面进行一次全方位的对比。作为工程师，做出正确的选择需要基于对数据结构和算法复杂度的深刻理解。

BFS (广度优先搜索)

:—

队列

层级扩散：先访问邻居，再访问邻居的邻居。

遵循 FIFO (First-In, First-Out)。

通常较高。假设树的最宽层有 N 个节点，队列需要存储 O(N)。最坏情况（满二叉树的最底层）是 O(N)。

寻找最短路径。在无权图中，BFS 第一次找到目标节点的路径一定是最短的。

当目标是“层级”相关时。例如：按层级打印树、社交网络中查看 1 度人脉、2 度人脉。

实际应用场景解析

让我们把视角拉回到实际开发中，看看这两种算法是如何解决真实问题的。

1. BFS 的实战应用：网络爬虫的最短路径

假设你在构建一个网络爬虫，从某个首页开始，你想找到到达某个特定目标页面的最少链接点击次数。这是典型的 BFS 应用场景。

• 为什么？ 因为网页链接构成了一个图。BFS 会先检查首页的所有直接链接（距离 1），然后检查这些链接指向的页面（距离 2）。只要第一次爬取到目标页面，你就可以确信这是点击次数最少的路径。DFS 在这里不仅效率低（可能陷入深层死循环），而且第一次找到的路径往往不是最短的。

2. DFS 的实战应用：解决数独或全排列问题

当你面对一个数独游戏，或者需要生成一个列表的所有全排列时，DFS 是最佳选择。

• 为什么？ 这类问题需要穷举所有可能的解。DFS 通过“尝试 -> 递归 -> 回溯”的模式，能够非常自然地遍历整个解空间树。BFS 在这种情况下会浪费大量的内存去存储中间状态，因为它需要把每一层的所有可能性都存下来，而 DFS 只需要维护当前路径上的状态。

性能优化与常见陷阱

作为开发者，我们在使用这两种算法时，有几个容易踩的坑需要特别注意：

• 递归深度限制 (DFS)：在 Python 等语言中，递归深度默认限制为 1000 层左右。如果你处理的树是极度倾斜的（退化成链表），直接使用递归 DFS 会导致 RecursionError。

* 解决方案：将递归改写为显式栈的迭代写法，或者设置更大的递归深度限制 sys.setrecursionlimit，但前者更安全。

• 队列内存开销 (BFS)：在处理大规模图或非常宽的树时，如果每一层有数万个节点，使用 BFS 可能会导致内存溢出 (OOM)。

* 解决方案：考虑使用 双向 BFS 或 迭代加深 DFS (IDDFS)，这两种算法在空间利用上更为激进，适合特定场景。

结论

BFS 和 DFS 不仅仅是在二叉树上跑来跑去的算法，它们代表了两种解决问题的核心思想：发散与专注。

• 当你想要“距离最近”、“层级清晰”，或者处理宽度较大的数据结构时，请优先考虑 BFS。不要忘记使用队列来管理你的待处理节点。
• 当你想要“穷举所有”、“深入细节”，或者数据结构偏向深度（或者你的内存比较紧张）时，DFS 是你的好帮手。无论是简洁的递归还是稳健的迭代，都能带你走遍每一个角落。

掌握了这两种遍历方式，你就打开了算法世界的大门。无论是处理文件系统目录、解析 HTML DOM 树，还是解决复杂的 LeetCode 题目，它们都是你最锋利的武器。建议你尝试手写一遍上述的迭代代码，感受一下队列和栈在节点流转中的魅力。