LeetCode 面试题 04.06. 后继者

2021-08-13 HGNULB 约 10 分钟

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

分类

LeetCode CodeTop 中等未解决 1-2 百度程序员面试金典（第 6 版）

题目描述

✅ 面试题 04.06. 后继者

题意分析

给定一棵二叉搜索树的根节点 root 和树中的某个节点 p，返回 p 在中序遍历下的下一个节点。如果 p 是中序遍历的最后一个节点（也就是整棵树里最大的），返回空。

约束里有三个必须读出来的信号。第一，这是二叉搜索树而不是普通二叉树——意味着可以靠值的大小关系直接决定往左还是往右走，不必遍历整棵树。第二，节点没有父指针，所以无法从 p 向上回溯，必须从根重新往下找。第三，题目保证 p 确实在树中，且 BST 里节点值互不相同，所以"中序后继"等价于"所有大于 p.val 的节点里值最小的那个"，这个等价转换是整题的钥匙。

边界上要覆盖：p 是最大节点（无后继，返回空）；p 有右子树（后继在子树内部，与祖先无关）；p 是某个祖先的左子树里的最右节点（后继就是那个祖先）；以及 p 就是根节点的两种情形（有无右子树）。

解法：利用 BST 性质定位后继

核心思路

暴力做法是完整跑一遍中序遍历，把节点按序存进列表，再找到 p 的位置返回下一个。它一定正确，但瓶颈明显：时间和空间都是 $O(n)$，完全没有用到 BST 的有序性——同样的代码放在普通二叉树上也能跑，说明它没抓住这题的考点。

关键观察是把"中序后继"翻译成值域上的语言：中序遍历 BST 得到的是升序序列，所以 p 的后继就是"值大于 p.val 的所有节点中，值最小的那个"。一旦转成这个描述，问题就从"遍历"变成了"查找"，可以像二分一样沿着一条根到叶的路径下行。

具体分两种情况，分别对应两个不同的不变量。

情况一：p 有右子树。 中序遍历访问完 p 之后，紧接着就要进入 p 的右子树，并且在右子树内部又是"先一路向左走到底"。所以后继就是右子树的最左节点。这个答案完全落在 p 的子树内部，与任何祖先无关——因为右子树里所有值都大于 p.val，而它们中最小的那个必然比任何祖先都更"紧贴"p。

情况二：p 没有右子树。 此时后继必然是 p 的某个祖先——具体说，是"最近的、把 p 放在自己左子树里的那个祖先"。因为把 p 放在左子树意味着该祖先的值大于 p.val，而 p 到根路径上所有"把 p 放在右子树里"的祖先值都小于 p.val，不可能是后继。

代码把这两种情况用一次自根向下的行走统一处理。维护变量 succ 表示"到目前为止见过的、大于 p.val 的最小值节点"，不变量是：每次循环结束时，succ 恰好是"已访问过的节点中，值大于 p.val 的最小者"，而尚未访问的部分全都落在 cur 所在的子树里。行走规则是：若 p.val < cur.val，说明 cur 是一个候选后继（它大于 p.val），先记下 succ = cur，然后往左找有没有更小的候选；否则 cur.val <= p.val，cur 及其左子树都不可能是后继，直接往右。走到空节点时，路径上所有可能的候选都已被考察，succ 就是答案（可能为空，表示 p 是最大节点）。

解题步骤

先处理"p 有右子树"这一情况，直接返回右子树的最左节点。之所以单独拎出来，是因为它有一条极短的确定路径，代码意图更清晰，也便于在面试里分情况讲解；顺带一提，即使去掉这个分支、只用后面的自根行走，答案同样正确——行走会自然地下降到右子树并在其中一路向左，但那样就把两种截然不同的情形糅在一起，讲解和验证都更费劲。

leftMost(node)：沿 left 一直走到底。循环条件写成 node.left != null 而不是 node != null，是为了返回最后一个非空节点而不是空指针。这个函数返回的正是"以 node 为根的子树中的最小值节点"。

否则从 root 出发，用 succ = null、cur = root 开始自顶向下行走。succ 初始化为空，这一步就已经把"p 是最大节点"的边界处理掉了：如果整条路径上从未出现过大于 p.val 的节点，succ 保持为空，直接作为答案返回。

p.val < cur.val 时记录 succ = cur 并转向左子树。记录是因为 cur 满足"大于 p.val"这个必要条件，是一个合法候选；转向左是为了寻找更小的候选——左子树里的值都比 cur 小，若其中还有大于 p.val 的，它会更接近 p，从而覆盖掉当前的 succ。

否则（cur.val <= p.val）转向右子树，且不更新 succ。cur 本身不大于 p.val，不是候选；它的整棵左子树的值更小，也全部出局。只有右子树里还可能藏着答案。

循环结束返回 succ。此时不变量保证 succ 已经是全树中大于 p.val 的最小节点，或者为空。

以下面这棵 BST 走一遍：根 5，左孩子 3（其左孩子 2、右孩子 4），右孩子 6。中序序列是 2, 3, 4, 5, 6。

查 p = 3（有右子树）：走情况一，leftMost(p.right) 从节点 4 出发，4.left 为空，直接返回 4。中序序列里 3 的下一个确实是 4，正确。

查 p = 4（无右子树）：进入自根行走。cur = 5：4 < 5 成立，succ = 5，转向左子树 cur = 3。cur = 3：4 < 3 不成立，转向右子树 cur = 4。cur = 4：4 < 4 不成立，转向右子树 cur = null。循环结束，返回 succ = 5。中序序列里 4 的下一个正是 5，正确。注意这里 succ 在第一步就被记下，之后再没有更优的候选出现——3 和 4 都不大于 4，被正确跳过。

查 p = 6（最大节点，无右子树）：cur = 5：6 < 5 不成立，转向右 cur = 6。cur = 6：6 < 6 不成立，转向右 cur = null。循环结束，succ 从未被赋值，返回空。正确——6 是中序最后一个节点。

查 p = 2（无右子树，后继是父节点）：cur = 5：2 < 5，succ = 5，转左 cur = 3。cur = 3：2 < 3，succ = 3（覆盖掉更远的 5），转左 cur = 2。cur = 2：2 < 2 不成立，转右 cur = null。返回 3，正确。这一步清楚展示了"往左走去找更紧的候选"的作用：若停在 5 不再深入，答案就会偏大。

代码实现

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right != null) {
            return leftMost(p.right);
        }

        TreeNode succ = null;
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val) {
                succ = cur;
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return succ;
    }

    private TreeNode leftMost(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
    if p.Right != nil {
        return leftMost(p.Right)
    }

    var succ *TreeNode
    cur := root
    for cur != nil {
        if p.Val < cur.Val {
            succ = cur
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }
    return succ
}

func leftMost(node *TreeNode) *TreeNode {
    for node.Left != nil {
        node = node.Left
    }
    return node
}

复杂度分析

时间复杂度：$O(h)$，h 为树高。两条路径都是自上而下单向行走，每步下降一层且绝不回头：情况一沿右子树的最左链下降，情况二从根沿一条路径下降到空。平衡树是 $O(\log n)$，退化成链时是 $O(n)$。

空间复杂度：$O(1)$。全程只用了 succ、cur 两个指针，没有递归、没有栈、没有存中序序列——这正是它优于"跑完整中序遍历"做法的地方。

关键点总结

把"中序后继"翻译成"大于目标值的最小节点"，是解锁 BST 的通用动作。一旦换成值域语言，遍历问题就变成查找问题，复杂度从 $O(n)$ 掉到 $O(h)$。中序前驱同理，翻译成"小于目标值的最大节点"，把代码里的比较方向和左右分支整体镜像即可。

"沿路径记录候选、边走边覆盖"是有序结构上找边界的标准模板。这和数组二分找"第一个大于 target 的位置"是同一个骨架：满足条件时记下答案并继续向更优的一侧收缩，不满足时直接排除半边。

没有父指针就必须从根重新下行。判断能否向上回溯，是树题选择解法的第一个岔路口：有父指针（如 510 题）可以直接沿父链向上找"第一个把当前节点放在左子树里的祖先"，$O(h)$ 但常数更小；没有就只能自根走一遍。

把 succ 初始化为空，就把"无后继"这个边界一并处理了。用哨兵值或额外标志位都不如"空即答案"来得干净——这是一类可迁移的写法：让默认值直接等于边界情形的正确答案，省掉一次特判。

面试视角：先分两种情况讲清中序后继的结构，再谈实现。面试官考这题看的就是你是否理解"有右子树看子树、无右子树看祖先"这个结构性结论。开口先说这两句，再说"因为没有父指针，第二种情况我改成从根出发边走边记候选"，思路链条完整；若被追问"能否用 $O(1)$ 空间且不分情况"，就答"可以，只保留自根行走那一段，它对两种情况都成立"。

易错点总结

错误写法：if (p.val <= cur.val) { succ = cur; cur = cur.left; }（用了 <=） → 用例：树 [5, 3, 6, 2, 4]，查 p = 4：走到 cur = 4 时 4 <= 4 成立，succ 被错误地更新成 4 自己并转向左子树，最终返回 4，正确答案是 5。后继必须严格大于 p.val，等号会把 p 自己当成答案。

错误写法：p.val < cur.val 时转向右子树（左右写反） → 用例：树 [5, 3, 6, 2, 4]，查 p = 2：2 < 5 记下 succ = 5 后转向右子树 6，2 < 6 又把 succ 更新成 6，最终返回 6，正确答案是 3。往左才能找到更紧的候选。

错误写法：succ 初始化为 root → 用例：树只有一个节点 [1]，查 p = 1：循环里 1 < 1 不成立直接转右走到空，返回 root 即节点 1 自己，正确答案是空。

错误写法：leftMost 的循环条件写成 while (node != null) node = node.left; → 用例：树 [5, 3, 6, 2, 4]，查 p = 3：一直走到空指针后返回 null，正确答案是节点 4。要返回最后一个非空节点，条件必须是 node.left != null。

错误写法：情况一写成 return p.right;（直接返回右孩子） → 用例：树中 p = 1，p.right 是 5 且 5 有左孩子 3：返回 5，正确答案是 3。右子树里最小的才是后继，必须再一路向左。

错误写法：情况一写成 rightMost(p.right)（走到最右） → 用例：p.right 是 5，其右孩子是 7：返回 7，正确答案是右子树的最小值。方向反了。

错误写法：不判 p.right != null 就调 leftMost(p.right) → 用例：查最大节点 p = 6：传入空指针后 node.left 抛 NPE（Go 里是 nil 指针解引用 panic）。

错误写法：把比较改成按引用判断 if (cur == p) ... 来定位 p 再取后继 → 用例：任意有右子树的 p：找到 p 之后仍然无法向上回溯（没有父指针），只能得到右子树内的答案，无右子树时直接返回空。引用定位丢掉了 BST 的有序性，等于自废武功。

错误写法：改用完整中序遍历存进 List 再线性查找 → 用例：n = 10^5 的链状树：时间和空间都是 $O(n)$，虽然能过但完全没用上 BST 性质；面试里会被要求重写成 $O(h)$ / $O(1)$ 的版本。

错误写法：Go 里写 succ := &TreeNode{} 而不是 var succ *TreeNode → 用例：查最大节点：返回的是一个值为 0 的假节点而不是 nil，判题会认为你返回了一个不存在的节点。表示"没有答案"必须用真正的空指针。

错误写法：把行走循环写成递归但忘了把 succ 沿调用链传下去/传回来 → 用例：树 [5, 3, 6, 2, 4]，查 p = 2：如果 succ 是局部变量，深层递归记录的候选无法带回上层，返回空。改递归时必须把 succ 作为参数下传或作为返回值上传。

相似题目

题目	难度	考察点
285. 二叉搜索树中的中序后继	中等	完全同题的主站版本，可对照"分两种情况"与"纯自根行走"两种写法
510. 二叉搜索树中的中序后继 II	中等	给了父指针但不给根，改成沿父链向上找第一个"左拐"的祖先
173. 二叉搜索树迭代器	中等	要连续输出后继，用显式栈缓存左链把均摊代价降到 $O(1)$
700. 二叉搜索树中的搜索	简单	同样自根下行，但目标是精确命中而非维护"最紧候选"
235. 二叉搜索树的最近公共祖先	中等	靠两个值与当前节点的相对位置决定走向，在"分叉点"停下
450. 删除二叉搜索树中的节点	中等	删除双子节点时正是用右子树最左节点（后继）来顶替