二叉搜索树中节点的前驱是比它小的最大节点：若有左子树，则为其左子树最右节点；若无左子树，则向上回溯找到首个作为右孩子的祖先，其父节点即前驱；无满足条件祖先时返回nullptr。
前驱节点的定义和判断逻辑
二叉搜索树中，某个节点的前驱是比它小的最大节点。关键在于：如果该节点有左子树，前驱就是左子树的最右节点；如果没有左子树，则要向上回溯，找到第一个“作为右孩子被访问”的祖先节点。
容易误判的是：把父节点直接当作前驱（错误！仅当当前节点是父节点的右孩子时才可能成立），或者忽略回溯路径中必须满足“从右分支上来”这一条件。
findPredecessor 函数的基本实现结构
假设节点结构为 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode* parent; };，带 parent 指针可大幅简化逻辑。不带 parent 时需额外传入根节点并递归/迭代查找路径。
- 若
node->left非空：循环向右走到node->left的最右节点 - 若
node->left为空：沿parent向上，跳过所有“是父节点左孩子的节点”，直到遇到第一个“是父节点右孩子”的节点，其父节点即为前驱 - 若一直回溯到根仍未满足条件，说明该节点是整棵树最小值，无前驱（返回
nullptr）
不带 parent 指针时的迭代查找写法
此时无法直接向上跳，得在向下查找过程中记录潜在候选者。核心思路是：边遍历边维护“当前已知的最大小于目标值的节点”。
示例逻辑片段：
TreeNode* findPredecessor(TreeNode* root, TreeNode* target) {
TreeNode* pred = nullptr;
TreeNode* curr = root;
while (curr) {
if (curr->val val) {
pred = curr; // 当前节点合法，暂记为候选
curr = curr->right; // 继续往更大的方向找，看能否逼近 target
} else {
curr = curr->left; // 当前太大，往左走
}
}
return pred;
}
注意：target 必须保证存在于树中（否则逻辑需额外校验）。这个版本不依赖 parent，但要求你知道 target 的 val 值——如果只给指针而树中可能有重复值，就存在歧义，需结合地址或额外标识判断唯一性。
容易踩的坑和边界情况
常见错误包括：对空树或单节点树未做防护、忽略 target 是最小节点时返回 nullptr 的合理性、在无 parent 版本中把 pred 更新时机写反（比如在 curr->val >= target->val 分支里更新）。
性能上，两种方式都是 O(h)，h 为树高；但带 parent 的版本在最坏情况下可能多几次指针跳转，而迭代版更缓存友好。
真正麻烦的是当树含重复值且未明确定义“前驱是否允许等于”——标准 BST 定义要求键唯一，所以实践中务必确认你的插入逻辑已排除重复 val。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
