DFS 与 BFS 一页速记（C++面试版）

一、核心概念

DFS（Depth First Search，深度优先搜索）

特点：

一条路走到黑
走不通再回退

典型实现：

递归
栈（Stack）

访问顺序示例：

      1
     / \
    2   3
   / \
  4   5

DFS:

1
↓
2
↓
4
↑
2
↓
5
↑
2
↑
1
↓
3

结果：

1 2 4 5 3

---

BFS（Breadth First Search，广度优先搜索）

特点：

按层搜索
逐层扩散

典型实现：

队列（Queue）

访问顺序示例：

      1
     / \
    2   3
   / \
  4   5

BFS:

第一层：
1

第二层：
2 3

第三层：
4 5

结果：

1 2 3 4 5

---

二、DFS 模板

返回值型 DFS

适用于：

最大深度
最小深度
节点数量
树高

模板：

int dfs(TreeNode* root)
{
    if(!root)
    {
        return 0;
    }

    int left = dfs(root->left);
    int right = dfs(root->right);

    return ...;
}

示例：104 最大深度

int maxDepth(TreeNode* root)
{
    if(!root)
    {
        return 0;
    }

    return max(
        maxDepth(root->left),
        maxDepth(root->right)
    ) + 1;
}

---

遍历型 DFS

适用于：

翻转二叉树
查找节点
路径问题

模板：

void dfs(TreeNode* root)
{
    if(!root)
    {
        return;
    }

    dfs(root->left);

    dfs(root->right);
}

---

三、BFS 模板

层序遍历标准模板：

vector<vector<int>> levelOrder(TreeNode* root)
{
    vector<vector<int>> result;

    if(!root)
    {
        return result;
    }

    queue<TreeNode*> q;

    q.push(root);

    while(!q.empty())
    {
        int size = q.size();

        vector<int> level;

        for(int i = 0; i < size; i++)
        {
            TreeNode* node = q.front();

            q.pop();

            level.push_back(node->val);

            if(node->left)
            {
                q.push(node->left);
            }

            if(node->right)
            {
                q.push(node->right);
            }
        }

        result.push_back(level);
    }

    return result;
}

---

四、为什么 BFS 要记录 size

关键代码：

int size = q.size();

作用：

记录当前层节点数量

例如：

队列：

[2,3]

说明：

当前层有2个节点

循环：

for(int i = 0; i < size; i++)

只处理这一层。

即使循环过程中：

q.push(node->left);
q.push(node->right);

新增了下一层节点，也不会影响当前层遍历。

---

五、DFS 与 BFS 对比

对比项	DFS	BFS
中文	深度优先搜索	广度优先搜索
思想	一条路走到底	一层一层搜索
常用数据结构	递归 / 栈	队列
空间复杂度	O(h)	O(n)
适合问题	深度、路径、子树	层序、最短路径
面试出现频率	极高	极高

---

六、如何判断用 DFS 还是 BFS

出现这些关键词

最大深度
最小深度
路径
祖先
直径
子树

优先考虑：

DFS

典型题：

104 最大深度
543 二叉树直径
236 最近公共祖先
112 路径总和
113 路径总和II

---

出现这些关键词

层序
每层
平均值
锯齿形
最近距离
最短路径

优先考虑：

BFS

典型题：

102 层序遍历
637 层平均值
103 锯齿形层序遍历

---

七、回溯与 DFS 的关系

回溯本质上也是 DFS。

普通 DFS：

dfs(root->left);
dfs(root->right);

---

回溯 DFS：

path.push_back(x);

dfs(...);

path.pop_back();

---

核心流程：

做选择
↓
递归搜索
↓
撤销选择

典型题：

77 组合
78 子集
39 组合总和
46 全排列
51 N皇后

---

八、面试速记口诀

DFS：

一条路走到黑
回头再找其他路

BFS：

一层一层向外扩散

回溯：

做选择
↓
递归
↓
撤销选择

判断题型：

层 → BFS

路径 → DFS

组合排列 → 回溯（DFS）