中序遍历非递归必须用栈，因为其“左→根→右”顺序要求访问根前必须探尽左子树，探到底后需回退至上一个待处理右子树的父节点，该回退路径只能靠栈显式保存；队列或数组无法维持这一后进先出的回溯逻辑。
为什么中序遍历非递归必须用栈
因为递归本质就是系统帮你维护了一个调用栈，中序遍历的顺序是「左→根→右」，访问根节点前必须先探完所有左子树，但探到叶子后需要回退到上一个有右子树的父节点——这个“回退路径”只能靠自己用栈显式存下来。不用栈而用队列或数组模拟，逻辑会失控，容易漏节点或重复访问。
std::stack 存什么：只存 TreeNode*，别存值
存指针才能后续访问其 left 和 right 成员；存值（如 int）就断了树结构，无法继续遍历。栈里永远只放尚未处理完右子树的节点，即“待回退点”。
- 初始把根节点压栈，然后一路向左走，每到一个节点就压栈，直到
nullptr - 弹出栈顶 → 访问它（输出/存入结果）→ 当前节点转向它的
right子树 - 对这个
right子树，重复“一路向左压栈”的动作
关键循环结构：外层 while + 内层 while
外层控制整个流程是否结束（栈空且当前节点为空），内层负责把一串左链全压进去。漏掉内层会导致只访问最左一条链，跳过所有右子树。
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<treenode> stk;
TreeNode* cur = root;
while (!stk.empty() || cur) {
while (cur) { // 内层：把左链全压栈
stk.push(cur);
cur = cur->left;
}
cur = stk.top(); // 弹出最左的，准备访问
stk.pop();
res.push_back(cur->val);
cur = cur->right; // 转向右子树，继续外层循环
}
return res;
}
</treenode></int></int>
常见错误：忘记判空、cur 更新位置错、重复压栈
典型报错是 member access within null pointer，基本都出在没检查 cur 是否为 nullptr 就直接访问 cur->left。还有人把 cur = cur->right 写在内层循环里，导致无限压空指针。
- 每次访问
cur->left或cur->right前，先确认cur != nullptr -
cur = cur->right必须在外层循环末尾，不能在内层 - 压栈只发生在内层
while (cur)中，绝不在外层重复压同一个节点
真正难的不是写出来，是理解“栈里存的是‘还没处理右子树’的节点”这一状态含义——只要这个认知模糊，调试时就会反复怀疑是栈操作错了，其实问题常出在 cur 的流转逻辑上。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
