非递归查找BST只需while循环沿单向路径比较并更新curr指针，找到返回节点、未找到返回nullptr；中序遍历必须用stack模拟调用栈，严格遵循“左到底→弹出访问→转右”逻辑，缺一不可。
非递归查找：用 while 循环模拟递归路径
二叉搜索树（BST）的查找本质是“比较→选边→继续”，完全不需要栈或递归。核心就是维护一个当前节点指针，不断比较 val 并向左或右移动。
常见错误是忘记判空或写错比较逻辑——比如把 root->val > target 时误走向右子树；或者循环条件写成 root != nullptr 却在循环内直接改 root，导致原始根丢失（实际无需保存原根，只要返回 nullptr 或找到节点即可）。
- 起始点必须是树根，每次只移动到
left或right，不回溯 - 比较后立即更新指针：
if (curr->val > target) curr = curr->left;，不是curr->left = ... - 循环退出条件是
curr == nullptr（没找到）或curr->val == target（找到）
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* curr = root;
while (curr != nullptr) {
if (curr->val == val) return curr;
else if (curr->val > val) curr = curr->left;
else curr = curr->right;
}
return nullptr;
}非递归中序遍历：用显式栈模拟系统调用栈
中序遍历“左→根→右”的非递归实现，关键在于：先一路压栈到最左节点，再逐个弹出并访问，每弹出一个就转向其右子树——这正好复现了递归的调用顺序。
容易踩的坑是右子树处理时机不对：有人在弹出后立刻压入 curr->right，但若 curr->right 为 nullptr，就会压入空指针，后续取栈顶解引用崩溃；正确做法是判非空再压。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 栈里存的是待访问的“根节点”，不是待处理的子树根
- 内层
while走左到底，外层while控制整体流程 - 每次从栈弹出后，先记录值，再检查
curr->right是否存在，存在才压入
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* curr = root;
while (curr != nullptr || !stk.empty()) {
while (curr != nullptr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top(); stk.pop();
res.push_back(curr->val);
curr = curr->right;
}
return res;
}为什么不能省略栈？纯指针遍历做不到中序
递归天然携带“返回上一层”的上下文，而纯指针只有父子关系，无法知道“访问完左子树后该回到哪个父节点”。没有栈（或等价结构如 Morris 遍历的线索化），就无法在访问完左子树+根之后，准确跳转到右子树——因为父节点信息已丢失。
Morris 遍历虽不用额外空间，但它会临时修改树结构（建立/拆除线索），破坏 BST 的原始形态，不适合需要保持树不变的场景（比如并发读、调试、或后续还要做插入/删除）。
- 标准非递归中序必须用
stack<TreeNode*>，空间复杂度 O(h)，h 是树高 - 若硬要 O(1) 空间，只能选 Morris，但得接受副作用：修改指针、线程不安全、不能用于 const 树
- 别试图用父指针数组替代栈——那只是换种方式存上下文，没减少空间
查找和遍历共用同一套节点结构，但意图完全不同
同一个 TreeNode 结构，searchBST 关心的是值比较与单路径剪枝，而 inorderTraversal 关心的是访问顺序与上下文恢复。两者看似都用 left/right，但驱动逻辑完全不同：一个是 BST 性质驱动的二分跳转，一个是中序定义驱动的栈式回溯。
实际工程中，如果既要查又要遍历，别强行合并逻辑——查找函数应专注快，遍历函数应专注顺序正确。混用会导致边界判断混乱，比如在查找循环里意外压栈，或在遍历栈操作中误做值比较。
真正容易被忽略的，是遍历时对空节点的防御性检查：压栈前判 curr != nullptr，弹出后判 curr->right != nullptr，少一个就可能段错误。这不是冗余，是必要守门员。
