递归dfs简洁直观但有栈溢出风险，需判空且避免误写终止条件；迭代dfs用stack模拟调用栈，压栈顺序关键，内存可控但代码稍长；两者时间复杂度均为o(n)，迭代版性能略优。
递归实现 DFS：简洁但要注意栈溢出风险
递归写法最直观，直接对应二叉树的定义：访问根节点后，递归遍历左子树、再右子树（前序），或按需调整顺序。核心是 dfs(node) 函数自身调用。
常见错误是忘记空节点判空，导致解引用 nullptr 崩溃；或者误把终止条件写成 node->left == nullptr && node->right == nullptr（只处理叶子），漏掉单子树分支。
- 前序遍历递归只需三行：
if (!node) return;→ 处理node->val→dfs(node->left)→dfs(node->right) - 递归深度 = 树的高度；链状退化树（如只有右子节点）下，
std::stack可能爆掉，Linux 默认线程栈约 8MB，但实际能承受的递归层数常低于 10⁵ - 不推荐在嵌入式或深度不确定的生产场景中无防护使用递归 DFS
迭代实现 DFS：用 stack 模拟调用栈，控制更明确
迭代靠 std::stack<treenode></treenode> 手动维护待访问节点，避免函数调用开销和栈限制。关键在于压栈顺序必须与目标遍历顺序一致——比如前序要先压右再压左，才能保证左子树先弹出。
容易踩的坑是混淆“访问”和“入栈”时机：DFS 要求节点一弹出就处理（即“访问”），不是入栈时就处理；否则会变成类似 BFS 的层序行为。
- 前序迭代模板：
stack.push(root); while (!stack.empty()) { auto n = stack.top(); stack.pop(); visit(n); if (n->right) stack.push(n->right); if (n->left) stack.push(n->left); } - 中序迭代需额外状态管理（比如记录“已访问左子树”），不能仅靠简单压栈；典型做法是沿左链一路 push 到底，再逐个 pop 并转向右子树
- 迭代版本内存占用可控（最多 O(h) 节点指针），但代码稍长，调试时可直接观察
stack内容，比递归更容易定位卡点
递归 vs 迭代：性能差异主要在调用开销与内存分布
现代编译器对尾递归优化有限（C++ 标准不强制支持），所以递归 DFS 几乎不会被优化成循环；两者时间复杂度都是 O(n)，但常数因子不同。
实测中，迭代版在大规模数据（>10⁶ 节点）下通常快 10%–20%，主因是避免了函数调用/返回的寄存器保存与恢复；而递归版局部变量（如参数）在栈帧里连续分配，缓存友好性略高，但差距微小。
- 递归版代码体积小、逻辑直白，适合教学、原型或已知树深
- 迭代版更适合服务端高频调用、实时系统或需严格控制最大内存占用的场合
- 若需同时支持多种遍历顺序（前/中/后），迭代实现容易因逻辑分支变多而出错；此时可考虑统一用「节点+状态」pair 入栈（如
std::stack<:pair int>></:pair>），但会增加内存与判断开销
后序遍历的特殊难点：迭代写法最容易出错
后序要求左右子树都访问完才处理根，而迭代中根最早入栈、却要最晚访问，天然存在顺序矛盾。强行用单栈需重复入栈或打标记，远不如递归自然。
典型错误是试图复用前序逻辑（只改压栈顺序），结果得到“根-右-左”的逆序，再 reverse 输出——这看似可行，但破坏了真正 DFS 的访问时序语义（比如做剪枝时无法及时响应子树结果）。
- 安全做法：用两个栈，第一个模拟前序，第二个接收其输出再倒序（即“根-左-右”→压入第二栈→最后依次弹出得“右-左-根”）
- 更通用解法：单栈存
std::pair<treenode bool></treenode>，bool表示“是否已处理过子树”，首次遇到设为 false 并压入左右子；第二次弹出且 flag==true 时才 visit - 除非业务强依赖后序时序（如释放内存、计算子树大小），否则优先用递归；迭代后序的可读性和维护成本明显更高
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
