非递归查找bst只需while循环沿单向路径比较，维护curr指针；中序遍历用stack模拟调用栈，需严格“左到底→弹出访问→转右”；前序先访后压右再压左；后序推荐双栈法；所有实现必须显式处理nullptr和const语义。
非递归查找：用 while 循环模拟递归路径
二叉搜索树（BST）的查找天然适合迭代——它本质就是沿着一条单向路径向下比较，不需要回溯。递归容易写错栈溢出或逻辑绕晕，非递归反而更可控、更易调试。
关键点是维护一个当前节点指针 curr，每次比较后只往左或右走一步：
- 若
curr->val == target，直接返回该节点指针 - 若
target val，令curr = curr->left - 若
target > curr->val，令curr = curr->right - 循环终止条件是
curr == nullptr，说明没找到
注意：别漏判空树（root == nullptr），否则 while 一开始就会崩。
中序遍历（非递归）：用 stack 模拟系统调用栈
中序遍历的非递归实现是最常考也最易错的。核心不是“压根再压右”，而是“一路向左到底，边走边压，触底后弹出并访问，再转向右子树”。这个顺序必须严格遵守，否则输出乱序。
典型错误是把右子节点直接 push 进栈——这会导致跳过中间节点，或者重复访问。
正确步骤：
- 初始化
stack<treenode></treenode>和curr = root -
while (!st.empty() || curr)是标准循环条件（栈非空 或 当前还有未处理分支） - 内层
while (curr)负责一路压左：压入curr，然后curr = curr->left - 弹出栈顶 → 访问该节点 →
curr = curr->right（注意：这里赋值的是刚弹出节点的右子，不是原curr）
示例片段：
stack<treenode> st;
TreeNode* curr = root;
while (!st.empty() || curr) {
while (curr) {
st.push(curr);
curr = curr->left;
}
curr = st.top(); st.pop();
cout val right;
}</treenode>
前序/后序非递归：前序简单，后序真麻烦
前序遍历非递归其实比中序还直观：先访问，再压右再压左（保证左先出栈）。但后序是三者中最难的，因为要等左右子树都处理完才访问根，光靠一个栈很难自然表达“已处理完左右”的状态。
常见做法是用两个栈，或用一个栈+标记位。推荐双栈法（清晰不易错）：
- 栈1用于BFS式遍历：压入
root，每次弹出后，按“左→右”顺序压入栈1 - 弹出元素全部压入栈2（反向存储）
- 最后逐个弹出栈2即为后序序列
单栈+pair
边界与兼容性：nullptr 处理和 const 正确性
所有非递归实现都依赖指针移动，一旦遇到 nullptr 就得立刻跳出循环或跳过操作。最容易被忽略的是：遍历时对空子树的判断必须显式写出，不能依赖“下一轮循环自动跳过”——比如在中序循环里漏了 if (curr) { ... }，就会对 nullptr 解引用崩溃。
另外，如果函数参数声明为 const TreeNode*，那么所有内部指针操作（如 curr = curr->left）必须保持 const 语义；若需修改树结构（如插入/删除），就不能用 const。混用会导致编译失败或隐式类型转换警告。
真正麻烦的不是算法本身，是每个指针操作前那半秒的条件检查——少一次 if (curr)，运行时就可能 core dump。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
