LeetCode 510. 二叉搜索树中的中序后继 II

2022-02-28 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 510. 二叉搜索树中的中序后继 II

题意分析

给定一棵二叉搜索树中的某个节点 node，返回它在中序遍历序列中的下一个节点；如果它已经是序列里的最后一个，返回空。与前一版最大的区别写在了函数签名里：这里拿不到根节点，只给了 node 本身，但节点结构体多了一个 parent 指针。

「没有根 + 有父指针」是这道题唯一的算法信号。没有根意味着不能做一次完整的中序遍历再找位置，也不能从上往下二分查找；有父指针意味着这棵树的连通性是双向的，从任意节点出发既能往下走也能往上爬。题目还额外要求「只用常数级别的额外空间」，这就把「先沿 parent 爬到根，再对整棵树做标准中序」这条退路也堵死了——那样是 $O(n)$ 时间且需要栈。所以答案必须只依赖 node 周围局部的结构信息。

边界上要覆盖：node 是整棵树中序序列的最后一个节点（即最右下角那个没有右孩子的节点），此时应返回空；node 是根且没有右子树（同样返回空）；node 是某个节点的左孩子且自身是叶子（后继就是它的父亲）；node 有右子树但右子树是一条向左的长链（要一路走到底）。题目保证 node 一定存在于树中，所以不用担心非法输入，但代码里对 node == null 做一层保护仍是好习惯。

解法：利用右子树与父指针

核心思路

先回忆中序遍历的定义：左子树 → 根 → 右子树。所谓「后继」，就是在这个递归展开出的线性序列里紧跟在 node 之后的那个节点。暴力做法是沿 parent 一路爬到根，然后跑一遍完整中序，边跑边记录上一个访问的节点，一旦发现上一个是 node 就返回当前节点。这个做法 $O(n)$ 时间、$O(h)$ 栈空间，正确但完全没用到「后继一定在 node 附近」这个事实。

瓶颈在于它把一个局部问题当成了全局问题。观察中序序列的生成过程：当递归刚刚「访问完」node 这个节点时，接下来立刻要做的事情只有一件——递归进入 node.right。所以只要 node 有右子树，后继必然落在右子树内部；而进入右子树后，中序又会一路先啃左子树，因此落点是右子树中「一直向左走到底」的那个节点，也就是右子树的最小值节点。这一步完全不需要知道 node 上方长什么样。

如果 node 没有右子树，说明以 node 为根的这棵子树在中序序列里已经彻底输出完毕，控制权要交还给上层。关键的观察是：递归从子树返回到父节点时，只有「从左子树返回」才会立刻访问父节点；「从右子树返回」意味着父节点早就被访问过了，控制权要继续上交。把这句话翻译成指针操作，就是沿 parent 向上爬，只要当前节点是它父亲的右孩子就继续爬；第一次遇到「当前节点是父亲的左孩子」时停下，这个父亲就是后继。如果一路爬到根（parent 为空）都没停下，说明 node 所在的位置是整棵树的最右链末端，中序序列已经结束，返回空。

于是维护的不变量是：向上爬的过程中，cur 始终满足「以 cur 为根的子树在中序序列里已全部输出完毕，且这段输出恰好以 node 结尾」。循环条件 cur.parent != null && cur.parent.right == cur 正是在维护这条不变量：从右孩子上升时，父子树的右半部分刚好走完，父节点连同它的左半部分更早就走完了，不变量得以扩张。循环退出时要么 cur.parent == null（无后继），要么 cur 是左孩子（cur.parent 就是后继），两种情况统一写成 return cur.parent 即可，非常整洁。

值得强调的是：整个解法只用到父子指针关系，完全没有比较过任何节点的值。这说明它对任意二叉树都成立，BST 的有序性在这里其实是多余条件——面试时主动点破这一点，是很好的加分信号。

解题步骤

先对 node == null 返回空。理由：虽然题目保证输入合法，但后续所有分支都要解引用 node，加一层保护能让代码在被复用时不崩，成本只有一行。

判断 node.right != null，成立则进入第一条路径。理由：这是中序递归的下一步动作，右子树非空时后继必定在其中，可以立刻剪掉向上爬的整条逻辑。

在第一条路径里，令 cur = node.right，然后 while (cur.left != null) cur = cur.left，返回 cur。理由：中序进入一棵子树后会先递归到最深的左端，那个没有左孩子的节点就是这棵子树第一个被访问的节点，也就是子树的最小值。

否则进入第二条路径，令 cur = node，执行 while (cur.parent != null && cur.parent.right == cur) cur = cur.parent。理由：这一步在把「已输出完毕的子树」不断向上扩张，每上升一层就吞掉一个「当前节点作为右子树」的父结构。

循环结束后直接 return cur.parent。理由：两种退出原因可以合并——若因 cur.parent == null 退出，返回值恰好是空，正确表示「没有后继」；若因 cur 是左孩子退出，cur.parent 恰好是那个还没被访问、马上要被访问的节点。不需要写两个 if 分开返回。

注意循环条件里两个判断的顺序不能交换：必须先判 cur.parent != null 再判 cur.parent.right == cur。理由：短路求值保证了根节点（parent 为空）不会被解引用，写反会直接空指针。

以一棵具体的树走一遍。树的形状是：根 5，左孩子 3（3 的左孩子 2、右孩子 4），右孩子 6。中序序列是 2, 3, 4, 5, 6。第一种情况，node = 3：3.right = 4 非空，进入右子树，4.left 为空，直接返回 4——与序列中 3 的后继一致。第二种情况，node = 4：4.right 为空，进入向上爬，cur = 4，4.parent = 3 且 3.right == 4 成立，上升到 cur = 3；再看 3.parent = 5 且 5.right 是 6 不是 3，条件不成立，循环退出，返回 3.parent = 5——与序列中 4 的后继一致。第三种情况，node = 6：6.right 为空，cur = 6，6.parent = 5 且 5.right == 6 成立，上升到 cur = 5；5.parent 为空，循环退出，返回 null——6 确实是中序序列的最后一个，无后继。

代码实现

class Solution {
    public Node inorderSuccessor(Node node) {
        if (node == null) {
            return null;
        }

        if (node.right != null) {
            Node cur = node.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }

        Node cur = node;
        while (cur.parent != null && cur.parent.right == cur) {
            cur = cur.parent;
        }

        return cur.parent;
    }
}

func inorderSuccessor(node *Node) *Node {
    if node == nil {
        return nil
    }

    if node.Right != nil {
        cur := node.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        return cur
    }

    cur := node
    for cur.Parent != nil && cur.Parent.Right == cur {
        cur = cur.Parent
    }

    return cur.Parent
}

复杂度分析

时间复杂度：$O(h)$，其中 $h$ 是树的高度。两条路径互斥且都只做单向移动：向下找最左节点最多走 $h$ 层，向上爬 parent 最多也是 $h$ 层，中间没有任何回溯或重复访问。平衡树上是 $O(\log n)$，退化成链时是 $O(n)$。

空间复杂度：$O(1)$。全程只用了一个游标指针 cur，两条路径都写成迭代循环而非递归，没有隐式调用栈，也没有开任何辅助容器，满足题目「常数级额外空间」的要求。

关键点总结

求中序后继的判定标准是「有没有右子树」：有右子树就取右子树的最左节点，没有就沿父链上升到第一个「作为左孩子」的位置。这个二分法同样适用于求中序前驱，只要把左右完全对调（有左子树取左子树最右节点，否则上升到第一个作为右孩子的位置）。

父指针把树从单向结构变成了双向可导航结构，这是「局部即可求解」的前提。凡是题面给了 parent 字段的树题，都要先问自己「能不能不看根节点就把答案算出来」，答案往往是可以，且能把 $O(n)$ 压到 $O(h)$。

把「两种退出原因」合并成同一个返回语句，是减少分支、避免遗漏的实用技巧。这里 return cur.parent 让「无后继」这个边界不需要单独写代码，是天然而非拼凑的统一。

循环条件里凡是出现 a.b.c 这种二级解引用，前面必须有对应的非空短路判断，且顺序不可交换。这是链式结构题的通用安全模式。

面试视角：微软很喜欢这题，因为它能在几分钟内区分「背过 BST 模板」和「真正理解中序递归的执行过程」。被问到时，最好的开场是画出中序递归的调用栈，指着「访问完 node 之后下一步做什么」来推导两条分支，而不是直接背结论。另外要主动指出「本解法没用到 BST 的值序，对任意二叉树都成立」，这句话往往就是面试官准备的追问。

易错点总结

错误写法：把向上爬的循环条件写成 while (cur.parent != null && cur.parent.left == cur)（左右写反）→ 用例树 5(3(2,4),6)，node = 4 → 4 是 3 的右孩子，条件不成立立刻退出，返回 4.parent = 3，但 3 是 4 的前驱不是后继，正确答案是 5。

错误写法：在有右子树的分支里返回 node.right 本身而不继续向左走到底 → 用例树中 node = 5，5.right = 8，8.left = 6 → 返回 8，但中序序列里 5 的后继是 6，答案偏大。

错误写法：向上爬时把循环条件的两个判断顺序颠倒成 while (cur.parent.right == cur && cur.parent != null) → 用例 node 是根且无右子树（如单节点树 [1]）→ 先解引用 cur.parent.right 时 cur.parent 已是 null，抛出空指针异常。

错误写法：向上爬结束后返回 cur 而不是 cur.parent → 用例树 5(3(2,4),6)，node = 4 → 上升到 cur = 3 后退出，返回 3，而 3 已经在中序序列里排在 4 之前，正确答案是 5。

错误写法：为了「保险」先沿 parent 爬到根，再对整棵树做递归中序找后继 → 用例一条含 $10^4$ 个节点的向右斜链 → 答案虽对，但时间退化到 $O(n)$、递归栈 $O(n)$，直接违反题目「常数级额外空间」的硬要求。

错误写法：用值比较代替结构判断，向上爬时写成 while (cur.parent != null && cur.parent.val < node.val) → 用例含重复值的树（如 2(2,3)，node 是左边那个 2）→ 父节点值等于 node.val，< 不成立，提前退出返回了错误节点；结构判断 cur.parent.right == cur 则不受重复值影响。

错误写法：在无右子树时只上升一层，直接 return node.parent 而不写循环 → 用例树 5(3(2,4),6)，node = 6 → 返回 6.parent = 5，但 5 早在 6 之前就被访问过了，正确答案是 null。

错误写法：Go 里比较父子关系用 *cur.Parent.Right == *cur 解引用后按值比较 → 用例树中存在两个值相同且左右孩子结构也相同的节点 → 按值比较可能对不同节点返回 true，上升方向判断错误；必须用指针相等 cur.Parent.Right == cur。

错误写法：把两条路径写成 if (node.right != null) {...} 之后没有 return，让控制流继续落入向上爬的逻辑 → 用例 node 有右子树时 → 先算出正确后继又被向上爬覆盖，最终返回祖先节点，答案错误。

错误写法：认为「树是 BST，后继就是比 node.val 大的最小值」，于是从 node 出发沿 parent 找到根再二分查找 → 用例无根输入 → 根本拿不到根节点；即使爬到根，也额外多花了 $O(h)$ 且逻辑更复杂，还在重复值场景下需要额外处理相等边界。

相似题目

题目	难度	考察点
285. 二叉搜索树中的中序后继	中等	给了根却没有父指针，只能自顶向下利用值序二分，思路与本题正好互补
LCR 053. 二叉搜索树中的中序后继	中等	同为无父指针版本，可练习「记录最后一次向左转的节点」这一种迭代写法
面试题 04.06. 后继者	中等	换成递归写法表达同一逻辑，考察递归返回值语义能否保持稳定
426. 将二叉搜索树转化为排序的双向链表	中等	把「求单个后继」推广成一次性把全部前驱后继指针串起来，需原地改指针
173. 二叉搜索树迭代器	中等	用显式栈支持反复调用 `next()`，是「后继」的可迭代化封装