后继节点是BST中比当前节点大的最小节点；若节点有右子树，则为其右子树最左节点，否则为向上回溯时第一个满足parent->left == current的祖先节点。
后继节点是什么，为什么不能只靠 right 指针
二叉搜索树（BST）中，某个节点的后继是比它大的最小节点。直觉上可能觉得“走右子树再一直往左”就行，但前提是该节点有右子树；如果 right == nullptr，就得向上回溯找“第一个作为左子节点被访问的祖先”——这个逻辑容易漏掉，导致返回空指针或错误节点。
关键判断点在于：后继要么在右子树的最左节点，要么在向上路径中第一个满足 parent->left == current 的父节点。
如何安全地实现 findSuccessor 函数
需要同时支持两种场景，且避免空指针解引用。假设节点结构为：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode *parent; // 必须有 parent 指针，否则无法向上查找
};
实操建议如下：
立即学习“C++免费学习笔记（深入）”；
- 先检查
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 上都稳定返回预期节点，尤其当插入/删除动态改变树结构之后。
