Keep Theme
算法学习-万物皆可搜（dfs/bfs/回溯）
Keep Team Lv4
  2026-02-25 15:23:54   2026-03-07 09:56:48

一、DFS（深度优先遍历）

1.1树形DFS

LeetCode 104 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

1
2
3
int maxDepth(TreeNode* root):
    if(!root) return 0;
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

没有使用到 visited 标记，直接DFS递归

LeetCode 112 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 

1
2
3
4
5
6
7
8
9
bool hasPathSum(TreeNode* root, int targetSum) {
       if(!root) return false;
       if(!root->left && !root->right){
           if(targetSum == root->val) return true;
           else return false;
       }
       targetSum -= root->val;
       return  hasPathSum(root->left,targetSum) || hasPathSum(root->right,targetSum);
}

假定从根节点到当前节点的值之和为val，我们可以将这个问题转换成是否存在从当前节点到叶子节点的路径，满足路径和为sum - val。

这满足了递归的性质，若当前节点是叶子节点并且其值val等于sum，则满足条件。若当前节点不是叶子节点，dfs访问左右节点即可

1.2网格/图 DFS

LeetCode 200 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        int dirx[4] = {-1, 0, 1, 0};
        int diry[4] = {0, 1, 0, -1};
        int ans = 0;
        auto dfs = [&](this auto&& dfs, int i, int j) -> void {
            visited[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int ni = i + dirx[k];
                int nj = j + diry[k];
                if (ni >= 0 && ni < row && nj >= 0 && nj < col &&
                    visited[ni][nj] == false && grid[ni][nj] == '1')
                    dfs(ni, nj);
            }
        };

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (visited[i][j] == false && grid[i][j] == '1') {
                    dfs(i, j);
                    ans += 1;
                }
            }
        }

        return ans;
}