前驱节点是BST中序遍历中位于目标节点前的节点，即比其值小的最大节点；有左子树时为其左子树最右节点，否则为查找路径上最后一个右拐的祖先。
什么是前驱节点，它在BST里长什么样
前驱节点是指中序遍历中位于目标节点 node 之前的那个节点。对 BST 来说，它要么是 node 左子树的最右节点（左子树存在时），要么是向上回溯过程中第一个“右拐”来的祖先（左子树为空时）。
注意：前驱节点一定比 node->val 小，且是所有比它小的值中最大的那个——这正是 BST 的结构性质决定的，不是靠遍历全树找出来的。
有左子树时怎么快速拿到前驱
如果 node->left 非空，前驱就在左子树里，而且一定是左子树的“最右叶子或非叶子节点”。不需要递归整棵树，只需一路向右：
TreeNode* predecessor = node->left;
while (predecessor->right) {
predecessor = predecessor->right;
}
// 此时 predecessor 就是前驱
- 这个过程时间复杂度是
O(h)，h是左子树高度，远优于中序遍历再查索引 - 别漏判
predecessor->right == nullptr的退出条件，否则空指针解引用 - 即使
node->left是个单链（只有 left 没 right），循环一次都不进，predecessor就是它自己——这也符合定义
左子树为空时怎么向上找“第一个右拐祖先”
这时得从根开始向下查找 node，同时记录可能的前驱候选。更实用的做法是：沿查找路径维护一个变量，每次往右走时更新它（因为往右意味着当前节点值比目标小，可能是前驱）：
立即学习“C++免费学习笔记（深入）”；
TreeNode* findPredecessor(TreeNode* root, TreeNode* node) {
TreeNode* pred = nullptr;
TreeNode* cur = root;
while (cur != node) {
if (cur->val < node->val) {
pred = cur; // 往右走，当前节点可能是前驱
cur = cur->right;
} else {
cur = cur->left;
}
}
// 找到 node 后，如果它有左子树，上面逻辑不适用，要另走左子树最右
if (node->left) {
cur = node->left;
while (cur->right) cur = cur->right;
return cur;
}
return pred;
}
- 这段代码假设你知道
node一定在树中；如果不确定，需先加查找逻辑或传入值而非指针 - 关键点：只在
cur->val val（即往右分支走）时才更新pred，往左走说明当前值太大，不可能是前驱 - 不能直接用 parent 指针简化——标准 BST 节点结构通常不含
parent，强行加会增加空间和维护成本
边界情况和容易错的点
前驱不一定存在。比如 node 是整棵树最小值（最左叶子），就没有前驱。返回 nullptr 是合理行为，但调用方必须检查：
- 对空树或
node == nullptr，直接返回nullptr - 如果
node是根且无左子树，且所有右子树节点都比它大，那前驱就是它自己？不——前驱必须严格小于，所以此时也返回nullptr - 不要混淆前驱（inorder 前一个）和父节点（parent）：二者完全无关，哪怕
node是右孩子，其父也不一定是前驱（比如父还有右子树） - 多线程环境下，若树被并发修改，查询结果可能不一致——这不是算法问题，而是数据结构使用前提没满足
真正难的不是写对逻辑，而是意识到：前驱只依赖局部结构（左子树最右 / 查找路径上的右拐点），而不是全局中序序列。一旦想成“先中序存数组再找 index-1”，就掉进 O(n) 和额外空间的坑里了。
