递归、迭代、morris遍历各适用不同场景：递归简洁但易栈溢出，适合小规模或高度可控树；迭代空间可控、无栈溢出风险，适合大规模数据；morris遍历空间o(1)，但需修改树结构，适用于超深树且允许非只读操作。
递归和迭代在 C++ 中不是“选哪个更好”，而是“哪个更合适”——关键看树高、内存约束、是否允许改结构、线程安全要求。
递归实现容易栈溢出，但代码最短
递归写法天然贴合二叉树定义，比如前序遍历三行就能写完：if (!node) return; → visit(node); → dfs(node->left); dfs(node->right);。但它的调用深度 = 树的高度 h，而 Linux 线程默认栈约 8MB，实际能撑住的递归层数常低于 10⁵。一旦树退化成单链（比如所有节点只有右子），Segmentation fault (core dumped) 很可能悄无声息就发生，连错误堆栈都来不及打印。
- 常见误写：把终止条件写成
node->left == nullptr && node->right == nullptr，漏掉只有一个子节点的分支，导致空指针解引用 - 适用场景：LeetCode 题目（数据规模 ≤ 10³）、调试阶段快速验证逻辑、AVL/红黑树等高度可控的结构
- 编译器几乎不优化它：C++ 标准不强制尾递归优化，
dfs(node->left)调用后还得保存现场回退，没法转成循环
迭代用 std::stack 模拟调用栈，压栈顺序不能错
迭代版用显式栈管理节点，空间占用可控（最多 O(h) 个指针），不会爆系统栈。但必须严格按目标遍历顺序压栈——比如前序要先压右子再压左子，否则弹出顺序就反了。中序更麻烦，不能只靠简单压栈，得配合“沿左链 push 到底 + pop 后转向右子”的两段逻辑。
- 关键陷阱：混淆“入栈”和“访问”。DFS 要求节点一
pop()就立刻visit()，不是入栈时处理；否则行为会趋近 BFS - 必须判空再压栈：
if (node->right) stack.push(node->right);，否则栈里混入nullptr，后续top()->left直接崩溃 - 性能实测：对百万级节点，迭代通常快 10%–20%，主因是省掉函数调用开销，但局部变量缓存友好性略逊于递归
Morris 遍历适合超深树，但会临时改树结构
当树高接近节点数（比如日志解析树深度达百万），std::stack 的 O(h) 空间也不够用，就得上 Morris 遍历。它复用叶子节点的空右指针建临时线索，全程只用几个指针变量，空间复杂度真·O(1)。
- 代价是会短暂修改原树：
cur->right = pre;这类操作不是只读，多线程环境下需加锁；有const接口要求时直接不可用 - 代码比普通迭代长，多了指针修复逻辑（比如恢复
pre->right = nullptr），运行稍慢但空间优势碾压 - 参数差异明显：函数体内没有递归调用，也没有容器，纯靠
while和指针移动推进
真正难的不是写出来，而是判断该用哪一种——输入树是否来自不可控来源？有没有并发访问？内存是否受限到连几万字节都要抠？这些细节一旦忽略，程序可能在线上跑几天才突然崩一次。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
