前驱节点是BST中序遍历中目标节点的前一个节点，即比其值小的最大节点；有左子树时为其左子树最右节点，无左子树时为向上回溯中首个作为右孩子的祖先节点。
什么是前驱节点，它在BST里长什么样
前驱节点指中序遍历中位于目标节点 node 前面的那个节点。对 BST 来说，它的本质是：比 node->val 小的所有值里的最大者。
所以分两种情况：
- 如果
node有左子树，前驱就是左子树的「最右节点」（即左子树中序遍历的最后一个） - 如果
node没有左子树，就得往上找——从父节点开始回溯，直到第一次「从右孩子返回父节点」的位置，那个父节点就是前驱
不带 parent 指针时怎么安全地向上回溯
多数实现中 TreeNode 不含 parent 字段，没法直接跳父节点。这时候必须边查找目标节点边记录路径，或者用递归隐式栈保存祖先信息。
推荐用递归方式，在查找过程中维护一个「可能的前驱候选」：
立即学习“C++免费学习笔记（深入）”；
- 初始候选为
nullptr - 每次向右走（说明当前节点值小于目标，可能是前驱）时更新候选为当前节点
- 每次向左走时候选不变
- 找到目标后，候选就是前驱；没找到则返回
nullptr
示例逻辑片段：
TreeNode* findPredecessor(TreeNode* root, int target) {
TreeNode* pred = nullptr;
while (root) {
if (root->val >= target) {
root = root->left;
} else {
pred = root;
root = root->right;
}
}
return pred;
}带 parent 指针时的简洁解法
如果有 parent 字段，逻辑更直观，但要注意两个分支的边界处理：
- 左子树存在 → 走到左子树的最右节点（循环
while (node->left)然后while (node->right)） - 左子树不存在 → 向上找第一个「是其父节点右孩子的祖先」，即
node == node->parent->right成立时，node->parent就是前驱 - 如果一路回溯到根都没满足条件，说明目标是整棵树最小值，无前驱 → 返回
nullptr
注意：判断 node->parent 是否为空必须放在每次访问前，否则会访问空指针。
容易被忽略的边界和性能坑
常见错误不是算法逻辑错，而是漏掉这些细节：
- 目标节点不存在时，不能假设返回的是某个默认值——必须明确返回
nullptr并由调用方处理 - 当目标是重复值节点（BST 允许重复？要看定义），前驱定义依赖于你如何插入重复值（左/右），务必统一规则
- 最坏时间复杂度是
O(h)，h 是树高；如果树退化成链表，就变成O(n)，别误以为一定是O(log n) - 用迭代写法时，别在更新
pred前忘记检查root非空——尤其在root = root->right后立刻用root判断
真正难的不是写出一个能跑通的版本，而是让所有边界 case（空树、单节点、目标为根、目标无左子树且父节点也无右分支……）都自然落入正确分支里。
