二叉搜索树中节点x的前驱是值严格小于x->val的最大节点，若x有左子树则为其左子树最右节点，否则为搜索路径上最后一个向右走的祖先节点。
前驱节点的定义和判断逻辑
二叉搜索树中，节点 x 的前驱是值严格小于 x->val 的最大节点。它只可能出现在两个位置：一是 x 的左子树中的最右节点（即左子树的“最大值”），二是从根向下查找 x 过程中最后一步向右走的祖先节点。
关键在于：如果 x 有左子树，前驱一定在左子树里，且是左子树的最右节点；否则必须向上回溯找“最后一个右拐”的父节点。
有左子树时直接找左子树最右节点
这是最简单的情况，无需回溯，时间复杂度 O(h)，h 是子树高度。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 从
x->left出发，不断向right走，直到right为nullptr - 注意边界：若
x->left == nullptr，直接跳过此分支 - 不要误写成“最左节点”——那是后继的逻辑
TreeNode* predecessor = x->left;
while (predecessor && predecessor->right) {
predecessor = predecessor->right;
}无左子树时需记录最近的右拐祖先
此时前驱不在左子树，只能是某个祖先，且该祖先必须满足：你从它出发向右走才最终到达 x。换句话说，它是搜索路径上最后一个“被跳过的右分支起点”。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 从根开始向下查找
x，用一个变量（如pre）记录每次向右走前的当前节点 - 向左走时更新
pre不必要；只有执行root = root->right前，才把当前root赋给pre - 查到
x后，pre就是前驱；若全程没右拐过（即x是整棵树最小值），则前驱不存在，返回nullptr
常见错误：把“上一个访问节点”或“父指针”当成前驱，但 BST 中节点通常不存父指针，且中序遍历缓存也不适用于单次查询场景。
完整查找函数的结构要点
合并两种情况时，不能先判断是否有左子树再单独处理——因为查找过程本身就能顺便收集右拐信息。更稳妥的做法是统一用迭代搜索，在找节点的同时维护候选前驱。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 初始化
pre = nullptr - 循环中：若目标值
val val，向左走；若val > curr->val，记录pre = curr再向右走；相等则退出 - 退出后，若
curr->left存在，仍需走一次最右查找——不能直接返回pre，因为左子树存在时前驱一定在内部 - 注意空指针检查：每一步访问
left或right前都要确认curr != nullptr
这个逻辑容易漏掉“有左子树就忽略 pre”这一层判断，导致返回错误祖先节点。
