如何找到二叉搜索树中某个节点的中序后继（或前驱）？

简化版

中序后继 = 中序遍历里紧跟在该节点之后的节点，也就是「比它大的最小节点」。分两种情况：① 若该节点有右子树，后继就是右子树里最左（最小）的节点；② 若没有右子树，后继是「从根往下找它的路径中，最后一个向左拐的祖先」。前驱对称：有左子树取左子树最右，否则取「最后一个向右拐的祖先」。

详细版

后继（successor）：比给定节点大的最小节点。

情况一：有右子树 → 后继是右子树的最左节点。

TreeNode succ = node.right;
while (succ.left != null) succ = succ.left;
// succ 即后继

情况二：没有右子树 → 从根开始查找该节点，记录「最后一次向左转」的节点，它就是后继。

TreeNode inorderSuccessor(TreeNode root, TreeNode target) {
    TreeNode succ = null, cur = root;
    while (cur != null) {
        if (target.val < cur.val) {
            succ = cur;              // 向左走时，cur 可能是后继，记下来
            cur = cur.left;
        } else {
            cur = cur.right;         // 向右走时不更新
        }
    }
    return succ;
}

这段代码其实统一处理了两种情况：无论有没有右子树，「最后一个让我们向左拐的节点」就是后继。若有右子树，答案会在向右下降后又向左的过程中被正确定位。

完整版教学

一、什么是中序后继/前驱

对 BST 做中序遍历得到升序序列，某节点的中序后继就是这个序列里它的下一个元素（比它大的数里最小的那个），中序前驱则是上一个元素（比它小的数里最大的那个）。它们在「BST 迭代器」「删除节点」「范围查询」里都要用到，是 BST 的基本操作。

二、后继的两种情况为什么这样分

想象在中序序列里，一个节点的「下一个」会出现在哪：

该节点有右子树：中序是「左根右」，访问完根（该节点）后紧接着进入右子树，而右子树里第一个被访问的是它的最左节点。所以后继 = 右子树最左节点。
该节点没有右子树：访问完它之后，中序遍历要「回溯到某个祖先」。具体是哪个祖先？是「该节点位于其左子树中的最近祖先」——因为访问完一个节点的左子树后，接下来就轮到这个祖先本身。等价于「从根向下查找目标时，最后一次向左转所在的那个节点」。

三、用「向左转」定位后继的技巧

第二种情况有个统一而巧妙的写法：从根出发查找目标节点，每当往左走（target < cur），就把当前 cur 记为候选后继；往右走则不记。查找结束时，最后记下的候选就是后继。

道理是：往左走意味着「cur 比 target 大」，cur 是一个「大于 target 的祖先」，而越往下这个候选越小、越接近 target，所以最后一次向左转的节点就是那个「最小的、比 target 大的祖先」，正是后继。这个写法连「有右子树」的情况也能正确覆盖，无需分支。

四、前驱是对称的

前驱（predecessor） = 比它小的最大节点：

有左子树 → 前驱是左子树的**最右（最大）**节点。
无左子树 → 从根查找目标，记录「最后一次向右转」的节点。

把后继逻辑的「左右」全部对调即可。

五、复杂度与应用

时间 O(h)：都是沿一条路径走，平衡时 O(log n)、最坏 O(n)。
应用：
- BST 迭代器：反复调用后继实现 next()。
- 删除有两个孩子的节点：用中序后继替换（见 BST 删除）。
- 范围查询：从下界节点开始不断取后继，直到超过上界。

若节点结构里带有父指针，找后继/前驱可以直接沿父指针回溯，不必从根开始。

六、常见误区与追问

考点	正确口径
有右子树	后继是右子树中最左节点
无右子树	后继是向上第一个把当前节点放在左侧的祖先
求前驱	把方向对称：左子树最右或向上第一个右祖先

successor(x):
  if x.right: return leftmost(x.right)
  while parent && x == parent.right: x = parent
  return parent

中序后继就是排序序列里的下一个节点，所有判断都围绕“比它大且最小”。

误区：后继一定是右孩子。 有右子树时要找右子树最左节点；右孩子本身不一定是最小的大值。
误区：没有右子树就一定没有后继。 可能存在某个祖先是后继，关键看当前节点是否位于这个祖先的左侧。
误区：前驱和后继需要完全不同的算法。 前驱是后继的镜像：有左子树找最右，否则向上找第一个右祖先。
追问：没有 parent 指针怎么办？ 可以从根出发搜索，遇到大于目标的节点就记录候选并向左走。
追问：复杂度是多少？ 无论从根搜索还是沿 parent 向上，最多走树高 h，复杂度 O(h)。
追问：这题和中序遍历有什么关系？ 中序后继就是 BST 中序升序序列里的下一个元素，只是不用真的生成完整序列。

七、加强记忆

中序后继 = 比它大的最小节点。有右子树→右子树最左；无右子树→查找路径上「最后一次向左拐」的祖先。统一写法：从根查找目标，每次向左走就记下当前节点为候选，最终候选即后继。前驱对称（有左子树取左子树最右，否则记「最后一次向右拐」）。O(h)。用于 BST 迭代器、删除节点、范围查询。

简化版

详细版