后继节点是bst中比当前节点大的最小节点；若节点有右子树，则为其右子树最左节点，否则为向上回溯时第一个满足parent->left == current的祖先节点。

后继节点是什么，为什么不能只靠 right 指针

二叉搜索树（BST）中，某个节点的后继是比它大的最小节点。直觉上可能觉得“走右子树再一直往左”就行，但前提是该节点有右子树；如果 right == nullptr，就得向上回溯找“第一个作为左子节点被访问的祖先”——这个逻辑容易漏掉，导致返回空指针或错误节点。

关键判断点在于：后继要么在右子树的最左节点，要么在向上路径中第一个满足 parent->left == current 的父节点。

如何安全地实现 findSuccessor 函数

需要同时支持两种场景，且避免空指针解引用。假设节点结构为：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *parent; // 必须有 parent 指针，否则无法向上查找
};

实操建议如下：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

• 先检查 node->right 是否非空：若存在，后继就是右子树的最左节点，用循环 while (cur->left) cur = cur->left 即可
• 若 node->right == nullptr，则从 node 开始向上遍历 parent，直到遇到 parent != nullptr && parent->left == node，此时 parent 就是后继
• 如果一路回溯到根节点都没满足条件（即当前节点是整棵树最大值），返回 nullptr
• 务必在每次访问 parent 前判空，例如 while (node->parent && node == node->parent->right) 是错的，应拆成两步防崩溃

没有 parent 指针时怎么办

标准 BST 节点常不带 parent，此时必须从根开始搜索，边走边记录“可能的后继候选”。这不是单纯递归找值，而是模拟中序遍历中的“下一个”行为：

• 初始化 successor = nullptr
• 从 root 开始迭代：if (root->val > target->val)，更新 successor = root，然后向左走；否则向右走
• 这个过程本质是“在下降路径中，把所有比目标大的节点视为候选，取其中最小的那个”，等价于中序序列里紧邻的下一个
• 时间复杂度仍是 O(h)，但无需额外空间存父链，适合无 parent 字段的场景

常见错误和调试线索

实际写的时候最容易栽在边界上：

• 输入 nullptr 未判，直接访问 ->right 或 ->parent 导致段错误
• 误把前驱逻辑套用到后继：比如写成 while (cur->right)，这是找最大值，不是后继
• 在无 parent 版本中，漏掉“更新 successor 只在向左走时发生”的条件，导致返回错误节点
• 测试时只用完全平衡树，没试 node 是叶子且无右子树、又位于最右路径末端的情况——这时必须回溯到空，返回 nullptr

真正难的不是写对一次，而是让 findSuccessor 在任意位置、任意形状的 BST 上都稳定返回预期节点，尤其当插入/删除动态改变树结构之后。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！