非递归查找BST只需while循环维护当前节点指针，依大小关系向左或右跳转，找到返回节点，未找到返回nullptr；中序遍历用栈模拟递归，先一路向左压栈，再逐个弹栈访问并转向右子树。
非递归查找：用 while 循环模拟递归路径
二叉搜索树（BST）的查找本质是沿 left 或 right 单向下降，完全没必要递归。核心就是维护一个当前节点指针，根据比较结果持续跳转。
常见错误是忘记判空或写错比较逻辑，比如把 val val 误写成 val val，导致重复键时行为不可控（BST 通常要求键唯一）。
- 初始化
curr = root，进入while (curr != nullptr) - 若
val == curr->val，直接返回curr - 若
val val，走左子树：curr = curr->left - 若
val > curr->val，走右子树：curr = curr->right - 循环结束仍未找到，返回
nullptr
非递归中序遍历：用栈显式保存“未访问的根”
中序遍历（左→根→右）的非递归实现依赖栈来暂存尚未处理的节点。关键不是“怎么压栈”，而是“什么时候弹栈并访问”。必须先一路向左走到头，再逐层回退、访问、转向右子树。
容易踩的坑是：在压栈后立即访问当前节点（混淆了前序逻辑），或者忽略右子树非空时需重新进入左探路循环。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 从
root开始，只要当前节点非空，就不断压栈并curr = curr->left - 栈顶弹出一个节点，访问它（如打印或存入 vector）
- 将
curr设为该节点的right，继续外层循环（即对右子树重复左探路） - 整个过程不递归，时间复杂度
O(n)，空间复杂度最坏O(h)（h 为树高）
统一用栈实现查找 + 遍历：避免重复构造辅助结构
如果既要查某个值，又要获取中序序列，不必分别写两套栈逻辑。中序遍历过程中一旦遇到目标值，可提前终止并返回节点——这比单独查找多花一点常数时间，但复用同一套栈操作更简洁。
注意：提前终止时栈里可能还有未弹出节点，但无需清理，函数退出即可。若后续还需继续遍历，应保存栈状态，但一般场景下不推荐混用。
- 遍历循环中，在访问节点前加判断：
if (curr->val == target) return curr; - 访问节点后才执行
curr = curr->right，确保不会跳过目标 - 若遍历完栈为空且未命中，说明不存在
迭代器风格封装：让中序遍历像 STL 容器一样用
真正实用的非递归中序，往往要封装成类似 std::vector::iterator 的接口。难点不在遍历本身，而在如何把“走到一半”的状态（栈 + 当前节点）打包成可拷贝、可比较的对象。
别试图在 operator++ 里每次都重建栈——那样是 O(h) 每次调用，性能差。正确做法是把栈作为成员变量，在构造和自增时增量维护。
- 构造时执行一次左探路，栈底存 root 路径上的所有左节点
-
operator++弹栈顶，访问；若其有右子树，则对该右子树再做左探路并压栈 -
operator*()返回栈顶节点的val（或指针），operator==比较两个迭代器的栈是否完全一致 - 迭代器失效问题：BST 插入/删除后，原有迭代器状态可能无效，这点和
std::map一致
h 接近 n，这时候栈深度也接近 n。别忘了空树边界处理——所有函数开头检查 root == nullptr。 
