递归虽简洁但禁用因其栈空间不可控、易栈溢出、调试困难；非递归中序遍历通过手动模拟调用栈，以“左路压栈→弹栈访问→右子树推进”实现可预测内存使用与中断安全。
为什么不能直接用递归，而要搞非递归
递归写法简洁，但实际项目里常被禁用：栈空间不可控、调试困难、嵌入式或实时系统中可能触发栈溢出。非递归中序遍历本质是手动模拟系统调用栈，核心在于「左路压栈 + 访问 + 右子树推进」——不是为了炫技，而是为了可预测的内存使用和中断安全。
std::stack 存什么节点最安全
存 TreeNode*（裸指针）最常用，但前提是能确保生命周期；若节点由智能指针管理（如 std::unique_ptr<treenode></treenode>），必须存 TreeNode* 而非 std::unique_ptr<treenode></treenode>，否则每次出栈会意外触发析构。切忌存引用或值拷贝——二叉树节点通常不含 trivial copy 语义，且体积大。
典型错误现象：use-after-free 或访问野指针，往往源于栈中保存了已移动或已释放的智能指针副本。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 统一用原始指针入栈，仅作临时导航，不承担所有权
- 若用
std::shared_ptr<treenode></treenode>，仍应存TreeNode*，避免循环引用或意外延长生命周期 - 初始化栈前确认根节点非空，空指针直接跳过，避免后续解引用崩溃
中序遍历非递归的核心三步怎么拆解
中序顺序是「左 → 根 → 右」，非递归的关键在于：不能等右子树处理完才访问根，而要在从左子树返回时立即访问——这靠「左路探到底 + 弹栈访问 + 切换到右子树」实现。
代码骨架如下（省略模板/命名空间）：
void inorderTraversal(TreeNode* root) {
std::stack<TreeNode*> stk;
TreeNode* curr = root;
while (curr != nullptr || !stk.empty()) {
// 1. 一路向左压栈，直到空
while (curr != nullptr) {
stk.push(curr);
curr = curr->left;
}
// 2. 弹栈并访问（此时左子树已全处理完）
curr = stk.top();
stk.pop();
visit(curr); // e.g., std::cout << curr->val << " ";
// 3. 切入右子树继续
curr = curr->right;
}
}
常见错误：
- 忘记在第二步后重置
curr = curr->right，导致死循环 - 把
visit()放在压栈循环内，变成前序遍历 - 判断条件写成
while (!stk.empty())却忽略curr，漏掉最右分支
如何支持返回 vector 而不只是打印
只需把 visit() 替换为 result.push_back(curr->val)，但要注意 vector 的容量预估。如果树深度已知或节点数可估算，用 result.reserve(n) 避免多次 realloc；否则默认行为也足够稳定。
性能影响点：
- 栈操作是 O(h) 空间复杂度（h 为树高），比递归更可控
- 每个节点最多入栈出栈各一次，时间仍是 O(n)，无额外开销
- 相比递归，少了函数调用帧的创建销毁成本，但现代编译器对尾递归优化有限，这点差异通常可忽略
真正容易被忽略的是边界：当树极度不平衡（如链表状），std::stack 内部仍会用动态内存分配，虽不爆栈，但频繁分配可能影响缓存局部性——这种场景下，若业务允许，考虑改用 Morris 遍历（O(1) 额外空间，需临时修改树结构）。
