中序前驱节点：若目标节点有左子树，则为其左子树最右节点；否则为搜索路径中最后遇到的比它小的祖先节点。中序后继节点同理，对称处理。
中序前驱节点怎么找（无父指针）
在没有父指针的 BST 中，findInorderPredecessor 的核心逻辑是：目标节点的前驱一定是其左子树的「最右节点」；如果它没有左子树，则需向上回溯——但因为没存父指针，必须边查找边记录可能的候选者。
实际做法是走一遍从根到 target 的搜索路径，同时维护一个 predecessor 变量：
- 每次向右走（
root = root->right），说明当前root的值比target小，可能是前驱，更新predecessor = root - 每次向左走（
root = root->left），不更新predecessor - 找到
target后，若它有左子树，最终答案是左子树的最右节点；否则就用上面保存的predecessor
注意：不能只依赖“左子树最右”，因为 target 可能是整棵树最小值，此时前驱不存在，应返回 nullptr。
中序后继节点怎么找（无父指针）
findInorderSuccessor 是对称操作，关键在于识别“比 target 大的最小值”落在哪：
- 每次向左走（
root = root->left），说明当前root比target大，可能是后继，更新successor = root - 每次向右走（
root = root->right），不更新successor - 找到
target后，若它有右子树，答案是右子树的最左节点；否则用保存的successor
常见错误是漏掉“有右子树”的分支判断，直接返回 successor，导致当 target 有右子时仍返回了路径上某个祖先——这显然不对，因为右子树里一定存在更近的后继。
为什么不能直接中序遍历一次存数组
虽然 inorderTraversal 得到有序数组后可以用二分查前驱/后继，但时间与空间开销都是 O(n)，而 BST 的结构本就支持 O(h)（h 为树高）查找。
- 单次查询：遍历数组是
O(n)，BST 路径查找是O(h)，退化成链表时最坏O(n)，但平均仍是O(log n) - 多次查询：预处理数组看似划算，但插入/删除节点后数组失效，而原生 BST 方法天然支持动态更新后的即时查询
- 内存压力：尤其在嵌入式或大节点场景下，额外
O(n)空间很敏感
所以除非你明确只查一次且树很小，否则别用数组缓存中序结果。
C++ 实现要注意的边界与写法
标准实现里容易忽略几个细节：
-
nullptr输入必须检查，否则解引用崩溃 - 查找过程中比较用
val还是地址？必须用值比较（root->val val），否则无法定位 - 递归写法易栈溢出，建议统一用迭代（while 循环），避免深树触发栈限制
- 返回的是节点指针，不是值——调用方要自己判空再取
->val，否则段错误
典型错误代码片段：if (root->left) return findMostRight(root->left); 忘了检查 root 是否为空；正确写法必须前置 if (!root) return nullptr;。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
