二叉搜索树中节点的前驱是中序遍历中排在其前面的最后一个节点：若有左子树，则为其左子树最右节点；否则为第一个满足该节点位于其右子树的祖先节点。
什么是二叉搜索树中的前驱节点
前驱节点指在中序遍历序列中，排在目标节点 node 前面的**最后一个节点**。它不一定是父节点或左子节点——比如当 node 有左子树时，前驱是左子树的最右节点；若没有左子树，则要沿祖先向上找第一个“右拐”来的祖先（即该祖先的右子路径经过了 node）。
如何用迭代方式安全查找前驱（避免递归栈溢出）
递归写法容易在退化成链表的树上爆栈，实际工程中更倾向迭代。核心逻辑分两步：先尝试在左子树里找最右节点；失败则回溯父路径。
- 从
node->left出发，持续向right走到底，最后非空节点即为前驱 - 若
node->left为空，需向上找：设cur = node，parent初始为空；循环中若cur是parent->right，则parent就是前驱；否则更新cur = parent，继续上跳 - 注意：必须提前保存每个节点的父指针，或在查找过程中动态维护（如用栈记录路径），否则无法回溯
为什么不能只靠 parent 指针就直接判断
有 parent 指针也不代表能跳一步得到答案。常见误判是“如果当前节点是右孩子，父节点就是前驱”——这仅在该父节点**没有左子树**时才成立。若父节点有左子树，且该左子树包含比 node 小但比父节点大的值，那前驱其实落在父节点左子树的最右处。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 错误写法：
if (node == node->parent->right) return node->parent; - 正确做法：即使有
parent，仍需检查node->parent->left是否存在，若存在，前驱必在其最右节点 - 所以真正可靠的路径是：先查左子树最右 → 再查祖先中第一个满足“当前节点属于其右子树”的那个祖先
带 parent 指针的 BST 节点定义与前驱实现示例
前提是节点结构含 parent，否则必须改用栈模拟路径。下面是最简可行实现：
立即学习“C++免费学习笔记（深入）”；
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode *parent;
TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
};
<p>TreeNode<em> inorderPredecessor(TreeNode</em> node) {
if (!node) return nullptr;
// Case 1: left subtree exists → max in left subtree
if (node->left) {
TreeNode<em> pred = node->left;
while (pred->right) pred = pred->right;
return pred;
}
// Case 2: no left subtree → find first ancestor where node is in right subtree
TreeNode</em> curr = node;
while (curr->parent && curr == curr->parent->left) {
curr = curr->parent;
}
return curr->parent; // if curr is right child, curr->parent is predecessor
}</p>最后一行的 curr->parent 容易被忽略空指针：若 node 是整棵树最小值（即中序第一个），curr 会一路跳到根，且根无 parent，此时返回 nullptr 才正确。
