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

2026-03-28 HGNULB 约 9 分钟

文章信息 2 个分类 4 个标签

分类

LeetCode 中等

题目描述

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

题意分析

题目目标：给一棵二叉搜索树的根 root 和树中的一个节点 p，返回中序遍历意义下 p 的下一个节点；若 p 是最大值，返回 null。

核心约束：题面给的是「中序后继」，但真正可利用的是 BST 的定义——中序遍历恰好是升序序列，所以「中序后继」等价于「树中所有严格大于 p.val 的节点里，值最小的那个」。这次转译是全题的分水岭：转成值域问题后，就不再需要遍历，只需要沿树下降。另外题目保证 BST 中节点值互不相同，所以可以放心地用值比较代替节点比较。

边界处理：p 是整棵树的最大值时没有后继，返回 null；p 是叶子节点、只有左子树、只有右子树三种形态都要覆盖；p 就是根节点时同样走一般流程。

实现取舍：可以老老实实做中序遍历并在找到 p 的下一个位置返回，$O(n)$ 时间且要遍历整棵树；也可以只沿一条路径下降，$O(h)$ 时间且不吃递归栈。BST 题给了有序性却不用，等于白给。

解法：深度优先搜索

核心思路

暴力做法是完整跑一遍中序遍历，用一个 prev 变量记住上一个访问的节点，当 prev == p 时当前节点就是答案。它正确、通用（对普通二叉树也成立），但完全没有利用 BST 的有序性，时间 $O(n)$、空间 $O(h)$ 的递归栈。

瓶颈在于「遍历」这个动作本身。既然已经把问题翻译成「求大于 p.val 的最小值」，就可以借助 BST 的分支性质做定向下降：站在任意节点 root 上，只有两种情况。

情况一，root.val > p.val。那么 root 是一个合法的候选答案——它确实大于 p.val。但它未必是最小的合法候选，因为它的左子树里可能还藏着更小的、同时又大于 p.val 的节点。于是记下这个候选，然后往左走继续找更优的。至于右子树，里面的值全都大于 root.val，比当前候选还大，直接整棵剪掉。

情况二，root.val <= p.val（由值互异，实际是 < 或 ==）。那么 root 及其整棵左子树的值都不超过 p.val，全部出局，答案只可能在右子树里，往右走，且不更新候选。

于是不变量是：answer 始终保存「已经考察过的节点中，大于 p.val 的最小者」，而尚未考察的部分永远落在当前 root 指向的子树内。每一步都把搜索范围砍掉一半路径分支，走到 null 时不变量给出的就是全局答案；如果一次都没有进入情况一，说明树里没有比 p.val 更大的值，answer 保持初始的 null，恰好就是「p 是最大值」的正确返回。

这个写法有一个常被忽略的好处：它完全不需要用到 p 的树内位置，只用了 p.val。所以哪怕只给一个数值而不给节点指针，代码也一字不改，这也是它比「先找到 p 再分情况讨论」的写法更简洁的原因——后者需要区分「p 有右子树」与「p 没有右子树」两大类，代码长一倍。

解题步骤

第一步：answer = null，root 从根开始。 为什么初值是 null：它同时承担了「还没找到任何候选」和「p 是最大值时的最终答案」两种含义，不需要额外的标志位。

第二步：循环条件 root != null，每轮做一次比较。 为什么用迭代而不是递归：这条下降路径是纯尾递归形式，改成循环后空间从 $O(h)$ 降到 $O(1)$，而且没有爆栈风险；BST 若退化成链表，$h$ 可达 $10^4$ 量级。

第三步：若 root.val > p.val，先 answer = root 再 root = root.left。 为什么先记录后左移：root 本身是当前已知的最优候选，左移是去寻找可能存在的更优候选，一旦左边什么也没找到，记下的这个就是答案。为什么可以丢掉右子树：右子树所有值都大于 root.val，而 root.val 已经是候选，右边不可能给出更小的合法值。

第四步：否则 root = root.right，且不动 answer。 为什么不更新候选：root.val <= p.val 不满足「严格大于」，它不是合法答案；同时它的左子树值更小，一并出局。

第五步：root 变成 null 时返回 answer。 为什么此时一定正确：不变量保证 answer 是所有已考察节点中的最优解，而循环结束意味着没有未考察的候选区域了。

以 root = [5, 3, 6, 2, 4, null, null, 1]、p 为值 4 的节点走一遍。这棵树的形状是：根 5，左孩子 3，右孩子 6；3 的左孩子 2、右孩子 4；2 的左孩子 1。中序序列是 1, 2, 3, 4, 5, 6，所以 4 的后继应当是 5。

初始 answer = null，root 指向 5。比较 5 > 4 成立，进入情况一：answer = 5，往左走到 3。这一步同时剪掉了整棵右子树（只有节点 6），因为 6 比 5 还大，不可能是更优候选。

root 指向 3。比较 3 > 4 不成立，进入情况二：不更新 answer，往右走到 4。这一步剪掉了 3 的左子树（节点 2 和 1），它们的值都小于 3，更小于 4，显然出局。

root 指向 4。比较 4 > 4 不成立（要求严格大于，这正是 p 自己不会被当成自己的后继的原因），进入情况二：往右走，而 4 没有右孩子，root 变成 null。

循环结束，返回 answer = 5，与期望一致。整条路径只访问了 5、3、4 三个节点，而不是全部 6 个。

再以同一棵树、p 为值 6 的节点走一遍：root = 5，5 > 6 不成立，往右走到 6；6 > 6 不成立，往右走，6 没有右孩子，root 变成 null。全程没有进入过情况一，answer 保持 null，正确地表达了「6 是最大值，没有后继」。

代码实现

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode answer = null;
        while (root != null) {
            if (root.val > p.val) {
                answer = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return answer;
    }
}

func inorderSuccessor(root *TreeNode, p *TreeNode) (answer *TreeNode) {
    for root != nil {
        if root.Val > p.Val {
            answer = root
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return
}

复杂度分析

时间复杂度：$O(h)$，$h$ 为树高，平衡时是 $O(\log n)$、退化成链表时是 $O(n)$。凭什么：每轮循环把 root 换成它的某个孩子，深度严格加一，所以循环次数不超过树高；循环体内只有一次比较和一次赋值。

空间复杂度：$O(1)$。凭什么：只用了 answer 和 root 两个指针变量，用迭代代替了递归，没有调用栈开销，也没有为中序序列开辟任何缓冲。

关键点总结

看到「中序后继」先把它翻译成「大于 p.val 的最小值」。 完成这次翻译，题目就从遍历题变成了查找题，$O(n)$ 立刻降到 $O(h)$。

BST 下降时「记录候选 + 往左收缩」是求上界类问题的通用模板。 对称地，求「小于某值的最大值」（中序前驱）只需把比较符号和左右分支同时反过来。

候选变量的 null 初值同时充当「无解」的返回值，省掉一个分支。 这类「让初值承担语义」的技巧在树和区间题里很常用。

尾递归形式一律改写成循环。 BST 退化时深度可达 $n$，迭代版本既省空间又不会爆栈，白板上也更容易写对。

只依赖 p.val 而不依赖 p 在树中的位置，是这个写法优于「分类讨论 p 有无右子树」的根本原因。 后者要处理两大类共四种子情形，出错面大得多。

面试视角：先说清楚「BST 中序 = 升序」这条桥梁，再给出 $O(h)$ 的下降写法。面试官通常会追问两件事：一是「如果节点带 parent 指针怎么做」（答案是 510 题：有右子树就取右子树最左端，否则一路向上直到成为某个节点的左孩子）；二是「如果不是 BST 而是普通二叉树呢」（只能退回中序遍历 + prev 指针的 $O(n)$ 做法）。这两个延伸能主动说出来，分数会明显不一样。

易错点总结

错误写法：比较写成 root.val >= p.val → 用例树 [5,3,6,2,4,null,null,1]、p 为 4，走到节点 4 时条件成立，answer 被设成 4 自己并往左走，最终返回 4，而正确答案是 5。

错误写法：情况一里先左移再记录，即 root = root.left; answer = root; → 用例同上，走到 5 时 answer 被记成 3 而不是 5，最终返回值偏小甚至可能是 null。

错误写法：情况二里也更新 answer = root → 用例同上，走到节点 3 时 answer 被覆盖成 3，返回 3，而 3 小于 p.val = 4，根本不是后继。

错误写法：情况一往右走、情况二往左走（分支写反） → 用例 p 为 4 时，5 > 4 后走到右孩子 6，再 6 > 4 走到 6 的右孩子 null，返回 6，跳过了真正的后继 5。

错误写法：answer 初始化为 root → 用例 p 为 6（最大值），全程不进入情况一，返回根节点 5，而期望 null。

错误写法：用节点引用比较 root == p 来定位 p 再分类讨论，但忘了「p 无右子树」的情形 → 用例 p 为 4（叶子，无右子树），找到 4 之后试图取 p.right 的最左端，直接返回 null，而正确答案是 5。

错误写法：先做完整中序遍历存进列表再线性查找 p 的下一个 → 用例是节点数 $10^5$ 的树时，时间和空间都退化到 $O(n)$；虽能通过，但在明确考察 BST 性质的题里等于放弃得分点。

错误写法：递归写成 return inorderSuccessor(root.left, p) 却在情况一里丢掉了已记录的候选 → 用例 p 为 4 时，从 5 往左递归进入以 3 为根的子树，子树内找不到任何大于 4 的节点返回 null，而根节点 5 这个候选没有被带回，最终返回 null。

错误写法：假设树中存在重复值并用 >= 处理 → 本题保证值互异，改成 >= 只会把 p 自己算进来；若真遇到允许重复的变体，正确做法是改用节点引用定位而非值比较。

错误写法：循环条件写成 root.left != null || root.right != null → 用例 p 为 4 时走到叶子节点 4 就退出，此时该往右走一步确认无右孩子的逻辑被跳过，虽然本例答案碰巧仍是 5，但若 p 是根且根为叶子，循环一次都不执行，返回 null 掩盖了真实情况。

相似题目

题目	难度	考察点
510. 二叉搜索树中的中序后继 II	中等	拿不到根节点但每个节点有 `parent` 指针，需要分「有无右子树」两种情形向上回溯
LCR 053. 二叉搜索树中的中序后继	中等	专题版同题，适合再用递归写一遍以对照迭代版的空间差异
面试题 04.06. 后继者	中等	同一模型的金典版本，常被要求当场同时给出中序遍历法与下降法两种解