非递归bst查找用while循环模拟递归路径，核心是维护curr指针并根据比较结果更新；中序遍历非递归需用stack模拟调用栈，遵循“左压栈→弹出访问→转右”逻辑；bstiterator应只读不管理内存，next()均摊o(1)但最坏o(h)。
非递归查找：用 while 循环模拟递归路径
二叉搜索树（BST）的查找本质是“比较→选边→继续”，完全不需要递归栈。核心是维护一个当前节点指针，每次比较后决定走向 left 还是 right，直到匹配或为 nullptr。
常见错误是忘记更新指针或提前 return 导致逻辑断裂；更隐蔽的问题是没处理空树（root == nullptr）直接解引用。
- 初始化
curr = root，进入while (curr != nullptr)循环 - 若
curr->val == target，直接返回curr或true - 若
target val，执行curr = curr->left - 否则（
target > curr->val），执行curr = curr->right - 循环结束仍未找到 → 返回
nullptr或false
中序遍历非递归：用 stack 模拟调用栈
中序遍历（左→根→右）的非递归实现依赖显式栈，关键在于“一路向左压栈，弹出即访问，再转向右子树”。这不是简单地把递归改成循环，而是重理解访问时机。
容易踩的坑包括：只压栈不走左子树、弹出后忽略右子树、重复压入同一节点（比如误在弹出后又压 curr->right 而不先设 curr = curr->right）。
- 初始化空
std::stack<treenode></treenode>和curr = root - 外层
while (curr != nullptr || !stack.empty()) - 内层 while：只要
curr非空，就stack.push(curr)并curr = curr->left - 弹出栈顶 → 访问（如
cout val）→curr = node->right
避免内存泄漏：迭代器风格封装时注意节点所有权
如果把非递归遍历包装成类（如 BSTIterator），必须明确谁负责释放节点内存。标准做法是只读访问，不管理生命周期；若自行 new 节点，务必配对 delete —— 但 BST 通常由用户控制内存，迭代器绝不应 delete 节点。
性能影响常被忽略：每次 next() 调用可能触发最多 O(h) 的栈操作（h 是树高），均摊仍是 O(1)，但最坏情况（退化为链表）下单次 next() 是 O(n)。若需稳定 O(1)，得预生成全部中序序列（牺牲空间换时间）。
-
BSTIterator构造函数中只做初始化，不遍历全树 -
next()内部复用上述中序逻辑，仅推进一步 - 不要在
next()中delete任何节点 —— 这不是它的职责 - 若 BST 节点含智能指针（如
std::unique_ptr<treenode></treenode>），确保移动语义正确，避免浅拷贝
调试时快速验证：打印栈状态和访问顺序
非递归逻辑一旦出错，很难靠脑补还原执行流。最有效的方式是在关键位置加日志，尤其观察栈大小变化和 curr 走向。
例如，在每次 stack.push(curr) 后打印 curr->val 和栈 size；在 stack.pop() 后打印弹出值；再打印转向的 curr->right->val（若存在）。这样能立刻发现“该压没压”或“该转没转”的问题。
- 临时插入
std::cout val - 弹出前加
std::cout val - 转向右子树前检查
if (curr) std::cout val - 测试用例优先选退化树（全左/全右）和单层树，比完全平衡树更容易暴露边界问题
stack 容器选 std::stack 就够用，别为了“通用”硬套 std::vector 手动模拟——除非你真要支持反向遍历或随机访问。非递归的核心价值是可控、可中断、无栈溢出风险，不是炫技。C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
