前驱节点是BST中值严格小于目标节点的最大节点；有左子树时为其左子树最右节点，无左子树时为向上回溯中首个作为右孩子的祖先节点，否则不存在。
前驱节点的定义与判断逻辑
二叉搜索树（BST）中，某节点 node 的前驱节点是值严格小于 node->val 的最大节点。它只可能出现在两个位置：
- 若
node有左子树，则前驱是左子树中的最右节点（即左子树的“最大值”） - 若
node无左子树，则需向上回溯，找到第一个“其右孩子路径通向node”的祖先节点
关键点在于：不能只看父指针是否存在，而要看路径方向。很多实现错误地假设只要存在 parent 指针就能直接往上跳，但若 node 是其父节点的左孩子，那父节点值更大，不是前驱。
带父指针时的前驱查找实现
当每个节点含 parent 成员时，逻辑清晰且无需额外空间：
若 node->left 非空：
- 从 node->left 开始，不断向右走直到 right == nullptr
- 返回最后访问的节点
否则（node->left == nullptr）：
- 沿 parent 向上，直到遇到第一个满足 current == current->parent->right 的节点
- 即：当前节点是其父节点的右孩子，此时父节点就是前驱
- 若一路走到根仍未满足条件，说明 node 是整棵树最小值，无前驱
TreeNode* inorderPredecessor(TreeNode* node) {
if (!node) return nullptr;
if (node->left) {
TreeNode* p = node->left;
while (p->right) p = p->right;
return p;
}
while (node->parent && node == node->parent->left)
node = node->parent;
return node->parent; // 可能为 nullptr
}
无父指针时如何安全查找前驱
没有 parent 指针时，必须从根开始搜索，同时记录可能的候选前驱：
立即学习“C++免费学习笔记（深入）”；
核心策略是模拟中序遍历路径：
- 初始化 pred = nullptr
- 从 root 出发，比较当前节点值与目标 node->val
- 若 cur->val val：该节点可能是前驱，更新 pred = cur，然后往右找更大的候选
- 若 cur->val >= node->val：往左找更小的值
注意：不能在相等时提前返回，因为要找的是“严格小于”的最大值，所以即使 cur == node，也要继续向左试探是否有更接近的候选（不过实际中 node 是树内已有节点，所以等于时应停止向左？不——你并不知道 node 的内存地址是否和 cur 相同，因此更稳妥的做法是传入目标值 target 而非节点指针；若必须用节点地址，则需额外比对指针）
典型误操作：把“找到值等于 node->val 的节点”当作搜索终点，忽略其左子树中仍可能存在合法前驱（比如 node 本身无左子树，但树中另有更小值节点未被检查）。正确做法是始终按 BST 性质推进，仅用值比较驱动方向。
边界与易错点提醒
常见崩溃点：
- 对空节点调用 node->left 或 node->parent 未判空
- 在无父指针版本中，把 pred 初始化为 root 而非 nullptr，导致最小节点返回自身
- 混淆前驱与前序遍历前一个节点：BST 前驱是数值意义上的前驱，不是遍历顺序的上一个（虽然中序下二者重合，但逻辑基础不同）
性能差异： - 有父指针：平均 O(h)，h 为树高，最坏 O(n)（退化链表） - 无父指针：必须从根开始，同样是 O(h)，但常数略大（每次都要重新进入子树）
真正容易被忽略的是：前驱不一定存在于 node 的子树中——它大概率在别处，尤其当 node 是左子树最右节点时，前驱就是它的父节点；而这个父节点，你得靠路径方向识别出来，不是靠大小比较。
