DFS在C++中用栈实现更稳妥，因递归易爆栈，而std::stack可精确控制深度与内存；递归仅适用于已知深度较浅的小规模场景。
DFS在C++中用递归还是栈实现更稳妥？
递归写法最直观，但容易爆栈；手动用std::stack能控深度，适合图大或树退化成链的情况。实际项目里，如果已知最大深度不超过几千，递归更简洁；否则优先选显式栈。
递归本质是系统帮你压栈，调用栈帧含返回地址、局部变量等开销；而std::stack只存你需要的节点（比如int或Node*），内存更可控。
- 递归：适合小规模、结构清晰的树遍历，如二叉树路径求和
- 显式栈：适合邻接表存储的大图、有环需判重、或嵌入式等栈空间受限环境
- 注意：递归版本必须设好终止条件，否则无限调用——常见错误是忘记检查
visited或空指针
邻接表上DFS怎么避免重复访问？
无向图或有向图含环时，不标记已访问节点会导致死循环。必须用std::vector<bool></bool>或std::unordered_set记录状态，且标记时机很关键：不是出栈/退出时标，而是入栈/进入函数时立刻标。
例如用std::stack<int></int>遍历图，每次pop()后对邻居循环，若邻居未访问，就push()并立即设visited[neighbor] = true。漏掉这步，同一节点可能被多次压入。
立即学习“C++免费学习笔记（深入）”；
- 错误写法：
if (!visited[n]) { stack.push(n); }—— 压入后没标，下次还可能再压 - 正确写法：
if (!visited[n]) { visited[n] = true; stack.push(n); } - 用
std::vector<bool></bool>比std::unordered_set快，尤其节点ID是连续整数时
DFS遍历树时如何传参才能不改原始数据？
常见需求是收集路径、判断是否存在某值、求最大深度等。不要用全局变量或引用参数来回传中间结果——易错且不可重入。推荐两种方式：
- 递归函数返回值：如
int dfs(TreeNode* root)返回子树高度，主调方直接用返回值组合结果 - 参数中传入非const引用仅用于收集，但必须明确命名，如
std::vector<int>& path</int>，并在进入/退出时做push_back()/pop_back() - 避免把
path作为值参传递，否则每层拷贝整个vector，时间复杂度飙升
例如找所有根到叶路径：void dfs(TreeNode* r, std::vector<int>& cur, std::vector<:vector>>& res)</:vector></int>，进函数加节点、叶子处res.push_back(cur)、出前cur.pop_back()。
为什么用DFS解连通分量却得到错误数量？
典型表现：调用一次dfs(start)后，仍有多余未访问节点，但代码却只计1次。根本原因是外层没遍历所有未访问节点——DFS本身只解决“从某点出发能到哪些点”，不自动覆盖全图。
正确做法是在主逻辑里用循环扫visited[]数组，对每个!visited[i]启动一次DFS，并累加连通分量计数。
- 错误：只对节点0调用一次
dfs(0)，就认为整个图处理完了 - 正确：for (int i = 0; i
- 特别注意：图可能不连通，或输入节点编号不连续（比如只有0、2、5存在），此时应基于实际存在的节点集合迭代，而非硬写
0..n-1
边界容易被忽略的是：空图（0个节点）要返回0，孤立节点算1个连通分量，这些得在循环前单独判断或靠循环自然覆盖。
