DFS 算法类型详细总结

1. 树形结构DFS（结构驱动）

特点：

• 驱动方式：由数据结构本身驱动（树的子节点）
• 递归调用：固定次数，由子节点数量决定
• 状态管理：通常不需要显式回溯
• 循环结构：通常没有循环

典型代码：

// 二叉树前序遍历
void dfs(TreeNode node) {
    if (node == null) return;
    
    process(node);          // 处理当前节点
    dfs(node.left);         // 递归左子树（固定）
    dfs(node.right);        // 递归右子树（固定）
}

// 多叉树遍历
void dfs(MultiTreeNode node) {
    if (node == null) return;
    
    process(node);
    for (TreeNode child : node.children) {  // 循环但由结构决定
        dfs(child);
    }
}

适用场景：

• 二叉树遍历（前序、中序、后序）
• 多叉树遍历
• 图的遍历（邻接表表示）
• 文件目录遍历

2. 回溯框架DFS（选择驱动）

特点：

• 驱动方式：由选择分支驱动
• 递归调用：可变次数，由选择数量决定
• 状态管理：需要显式的选择/撤销选择（回溯）
• 循环结构：必须有循环遍历选择

典型代码：

// 子集问题
void dfs(int idx, int[] nums) {
    ans.add(new ArrayList<>(cur));
    
    for (int i = idx; i < nums.length; i++) {  // 遍历选择
        cur.add(nums[i]);      // 做选择
        dfs(i + 1, nums);      // 递归
        cur.removeLast();      // 撤销选择（回溯）
    }
}

// 迷宫问题
void dfs(int x, int y, int[][] maze) {
    if (到达终点) 记录结果;
    
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] dir : dirs) {   // 遍历方向选择
        int nx = x + dir[0], ny = y + dir[1];
        if (可走(nx, ny)) {
            maze[nx][ny] = 1;  // 做选择（标记）
            dfs(nx, ny, maze);
            maze[nx][ny] = 0;  // 撤销选择（回溯）
        }
    }
}

适用场景：

• 组合问题（子集、组合求和）
• 排列问题（全排列）
• 棋盘问题（N皇后、数独）
• 路径问题（迷宫、图的最短路径）
• 分割问题（回文分割）

如何理解"生成新结构"

核心概念：从"遍历已有"到"构建未知"

1. 树形结构DFS：遍历已有结构

// 遍历二叉树 - 结构是已知的、固定的
void dfs(TreeNode node) {
    if (node == null) return;
    System.out.println(node.val);  // 处理已有的节点
    dfs(node.left);               // 遍历已有的左子树
    dfs(node.right);              // 遍历已有的右子树
}

特点：结构在调用DFS前就已经存在，只是去访问它。

2. 回溯框架DFS：生成新结构

// 生成子集 - 结构是动态构建的
void dfs(int idx, int[] nums) {
    ans.add(new ArrayList<>(cur));  // 当前构建的子集
    
    for (int i = idx; i < nums.length; i++) {
        cur.add(nums[i]);          // 选择元素，构建新结构
        dfs(i + 1, nums);          // 继续构建
        cur.removeLast();          // 撤销选择，尝试其他构建方式
    }
}

特点：结构在DFS过程中动态创建和修改。

具体理解角度：

角度1：结果空间的构建

• 树形DFS：结果空间是输入结构的各种遍历顺序
• 回溯DFS：结果空间是所有可能的组合/排列/子集

角度2：状态的变化

• 树形DFS：状态是当前访问位置，在已有结构中移动
• 回溯DFS：状态是当前构建的部分解，在不断扩展和收缩

角度3：决策的过程

• 树形DFS：没有决策，只有固定的访问顺序
• 回溯DFS：每一步都有多个选择，需要决策和回溯

生动比喻：

🎯 树形DFS：像"参观博物馆"

• 展品（节点）已经布置好了
• 你只是按照某种顺序参观它们
• 不需要改变展品的摆放

🛠️ 回溯DFS：像"用积木搭建各种造型"

• 积木（元素）是给定的
• 但你要尝试不同的搭建方式（组合）
• 可以拆掉重搭（回溯）
• 最终产生很多不同的造型（新结构）

走迷宫问题属于回溯框架的DFS（选择驱动）。

迷宫DFS的典型写法：

private void dfs(int x, int y, int[][] maze) {
    // 终止条件：到达终点或越界
    if (x < 0 || x >= maze.length || y < 0 || y >= maze[0].length || maze[x][y] == 1) {
        return;
    }
    if (x == targetX && y == targetY) {
        // 找到路径，记录结果
        return;
    }
    
    // 标记已访问
    maze[x][y] = 1;
    
    // 四个方向的选择分支
    dfs(x + 1, y, maze);    // 向下
    dfs(x - 1, y, maze);    // 向上
    dfs(x, y + 1, maze);    // 向右
    dfs(x, y - 1, maze);    // 向左
    
    // 回溯：撤销标记
    maze[x][y] = 0;
}

为什么属于第4种（回溯框架）？

1. 选择驱动：有多个移动方向（上、下、左、右）可以选择
2. 显式回溯：需要标记访问和撤销标记
3. 循环结构：虽然这里用多个DFS调用代替了循环，但本质是遍历所有可能的选择
4. 状态管理：需要管理访问状态，防止重复访问

与树形DFS(3)的区别：

• 树形DFS：递归调用由数据结构决定（左子树、右子树）
• 迷宫DFS：递归调用由选择分支决定（四个方向），需要显式回溯

更标准的迷宫回溯写法（使用循环）：

private void dfs(int x, int y, int[][] maze) {
    if (到达终点) {
        记录路径;
        return;
    }
    
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    for (int[] dir : directions) {  // 循环遍历所有方向选择
        int nx = x + dir[0];
        int ny = y + dir[1];
        
        if (可以走(nx, ny, maze)) {
            maze[nx][ny] = 1;      // 做选择
            dfs(nx, ny, maze);     // 递归
            maze[nx][ny] = 0;      // 撤销选择
        }
    }
}

所以走迷宫问题属于回溯框架的DFS，因为它涉及多个选择分支和显式的状态回溯。