- 正确答案：DFS（深度优先搜索）是一种遍历或搜索图/树的算法，其核心是“一条路走到黑，撞墙才回头”，借助栈（递归调用栈或显式栈）实现。针对三种典型场景——二叉树遍历（*）、迷宫路径求解（y）、全排列生成（n），虽然都基于DFS思想，但建模方式、状态定义、剪枝策略和终止条件存在本质差异：（1）二叉树DFS（*）：以节点为状态，递归访问左子树→右子树（前序/中序/后序），无环、无重复访问、无需visited数组；时间复杂度O(n)，空间复杂度O(h)（h为树高，即递归栈深）。（2）迷宫DFS（y）：以二维坐标(r, c)为状态，在网格图中沿上下左右四个方向扩展；需维护visited矩阵防环/重访；常需回溯（进入时标记，退出时撤销）；可能要求最短路径（此时DFS不适用，应改用BFS），但若只判断“是否存在路径”或求“任意一条路径”，DFS可行；时间复杂度最坏O(4^(m*n))，但加剪枝（如障碍、越界、已访问）后实际可控。（3）全排列DFS（n）：以“当前排列path”和“剩余可选数字集合”为状态；每层从剩余数中选一个加入path，递归进入下一层；递归终点是path长度等于原数组长度；需used[]布尔数组或set记录已选数字（避免重复使用同一元素）；若原数组含重复元素且要求去重全排列，则需先排序 + 剪枝：if i > 0 && nums[i] == nums[i-1] && !used[i-1] → skip（保证相同元素按顺序选取，避免分支等价）；时间复杂度O(n! × n)（n!个排列，每个拷贝path耗O(n)）。 - 解答思路：第一步，识别问题抽象模型——是树形结构（天然无环，父子关系明确）？还是隐式图（格点/状态转移图，可能含环）？还是组合状态空间（排列/子集/组合）？第二步，定义DFS状态（state）：二叉树是TreeNode*；迷宫是(row, col) + grid + visited；全排列是(path, used, depth)。第三步，确定递归基（base case）：二叉树为node == null；迷宫为(r,c)越界/障碍/已访问/到达终点；全排列为path.size() == n。第四步，设计选择与回溯：二叉树自动左右递归，无需显式回溯（因节点不可复用）；迷宫需在进入邻居前标记visited[r][c]=true，返回前设为false；全排列需在for循环中used[i]=true → dfs() → used[i]=false。第五步，考虑剪枝优化：迷宫可加启发式（如曼哈顿距离剪枝）；全排列可排序+相邻重复剪枝；二叉树一般无需剪枝（除非题目要求如“找某值路径”，则找到即可return true提前终止）。 - 深度知识讲解：【底层数据结构支撑】 DFS本质依赖栈结构。递归实现利用系统调用栈，每一帧保存局部变量（如当前节点指针、坐标、path副本、used数组引用等）；迭代实现需手动维护stack，其中元素类型取决于问题：二叉树可存TreeNode*；迷宫存pair；全排列需存结构体{vector path; vector used;} 或压缩编码（如bitmask，当n≤20时可用int表示used状态）。【递归与回溯的本质区别】 “递归”是函数调用自身的控制流机制；“回溯”是算法设计范式，特指在DFS中**试探性选择→递归深入→失败则撤销选择**的过程。二叉树遍历通常不称“回溯”，因其无“撤销”动作（节点访问是单向的）；而迷宫和全排列必须回溯——因为同一格子/数字在不同分支中可能被多次尝试，必须恢复现场供其他分支使用。回溯的正确性依赖于“状态可逆性”，即used[i] = false必须执行，否则污染兄弟分支。【时间复杂度的精确分析】 - 二叉树DFS：每个节点访问1次 → O(n)。 - 迷宫DFS：最坏情况遍历所有路径，网格有m×n个格子，每个格子最多4个出边，但因visited限制，实际每个格子最多被访问1次 → 理论上仍是O(m×n)，但路径数量级是指数级（如空网格中从起点到终点的路径数≈C(m+n-2, m-1)），故若不限制路径长度或不剪枝，DFS可能超时。注意：DFS不保证最短路径，BFS才是层序扩展，天然满足最短性。 - 全排列DFS：递归树共n层，第0层1个节点，第1层n个节点，第2层n×(n−1)个……第n层n!个叶子 → 总节点数 = Σ_{k=0}^n P(n,k) = O(n!)，每叶子生成1个排列（O(n)拷贝），故总时间O(n×n!)。若用引用+pop_back()避免拷贝，可优化至O(n!)。【常见错误与陷阱】 - 迷宫DFS忘记重置visited（导致后续路径不可达）； - 全排列未用used数组，导致同一数字重复使用（如[1,2,3]生成出[1,1,1]）； - 二叉树DFS中误将root==null作为唯一出口，却在递归前未判空导致空指针解引用； - 对含重复元素数组做全排列时，仅用used[i-1]==false剪枝（错误！应为used[i-1]==false表示前一相同元素未被使用，说明当前分支是“跳过前一个”的等价分支，必须剪），正确条件是：if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) —— 此保证相同元素按索引顺序被选取，消除重复排列。 - 代码示例（统一用C++风格伪代码，强调核心逻辑）： // 二叉树前序遍历DFS（递归） void dfs(TreeNode* node) { if (!node) return; visit(node); // 处理当前节点 dfs(node->left); // 递归左子树 dfs(node->right); // 递归右子树 } // 迷宫DFS（判断是否存在路径，grid为vector>，'.'可走，'#'障碍，'S'起点，'E'终点） bool dfs_maze(vector>& grid, vector>& visited, int r, int c, int tr, int tc) { if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size()) return false; if (grid[r][c] == '#' || visited[r][c]) return false; if (r == tr && c == tc) return true; visited[r][c] = true; // 标记已访问 // 四方向递归 bool res = dfs_maze(grid, visited, r-1, c, tr, tc) || dfs_maze(grid, visited, r+1, c, tr, tc) || dfs_maze(grid, visited, r, c-1, tr, tc) || dfs_maze(grid, visited, r, c+1, tr, tc); visited[r][c] = false; // 回溯：撤销标记（若只需判断存在性，此处可省略；但若需记录路径，则必须） return res; } // 全排列DFS（无重复元素，返回所有排列） vector> result; vector path; vector used; void dfs_permute(const vector& nums) { if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i]) continue; used[i] = true; path.push_back(nums[i]); dfs_permute(nums); path.pop_back(); // 回溯：撤销选择 used[i] = false; } } // 全排列DFS（含重复元素，需剪枝） void dfs_permute_unique(const vector& nums) { if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // 关键剪枝 used[i] = true; path.push_back(nums[i]); dfs_permute_unique(nums); path.pop_back(); used[i] = false; } }

华为od+科锐国际+参考题2

全站热榜

创作者周榜