LeetCode 面试题 04.06. 后继者

约 4 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 程序员面试金典（第 6 版） 百度
标签
深度优先搜索 树 二叉树 二叉搜索树

题目描述

✅ 面试题 04.06. 后继者

image-20260929105803594

题意分析

返回二叉搜索树中指定节点 p 在中序遍历后的下一个节点。搜索树的中序序列严格递增，所以等价于寻找值严格大于 p.val 的最小节点；如果 p 已是最大节点，则返回空。

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

核心思路

[!blue]
先看 p 是否有右子树。 中序顺序是左子树、当前节点、右子树，所以访问完 p 后，如果右子树存在，下一步一定进入右子树。沿它的左孩子不断向下，就能找到其中最先访问、也就是值最小的节点，这就是后继；不能直接认定右孩子就是答案。

没有右子树时，后继只能来自祖先：它是从 p 向上看，第一个把 p 放在自己左子树中的祖先。节点没有父指针，可以反过来从根向下搜索，同时用 succ 保存目前遇到的后继候选。

若 cur.val > p.val，当前节点符合“严格更大”，先保存为候选。它的右子树更大，不可能比当前候选更接近 p，因此继续去左子树寻找更小的合格值。若 cur.val <= p.val，当前节点及整个左子树都不合格，只能去右子树。

每次转向都排除不合格节点，或排除不会优于当前候选的节点，因而不会丢失最小的较大值。最终走到空位置时，succ 就是后继；始终未找到大于 p 的节点时，它保持为空。相等时必须走右侧，不能把 p 自己记为候选。

解题步骤

  1. 若 p 有右子树，返回其最左节点。
  2. 否则从根开始，候选初始化为空。
  3. 当前节点值大于 p.val 时更新候选并向左；否则向右。每轮只进入一个子树。
  4. 走到空位置后返回候选。最大节点没有右子树，搜索过程中也不会产生候选，正好返回空。

代码实现

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)$。

关键点总结

[!green]

  • 后继必须严格更大，不能返回 p 自己。
  • 记录候选后还要向左寻找更接近的值。
  • 无后继使用空指针表示，不创建虚假节点。

易错点总结

[!yellow]

  • 比较使用小于等于：遇到 p 时会把自己记录为后继。
  • 有右子树就直接返回右孩子：右孩子的左侧还可能有更小节点。
  • 候选初始化为根：最大节点可能错误返回一个无关节点。
  • 保存候选后转向右侧：会寻找更大的值而非更小后继。

相似题目

题目 难度 关联与区别
173. 二叉搜索树迭代器 中等 中序迭代器能够依次取得后继，本题只查询一次，直接沿 BST 查找无需展开整个序列。
230. 二叉搜索树中第 K 小的元素 中等 同样利用 BST 中序升序性质，第 k 小还需要统计遍历位置，本题用目标值直接导航。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/72481693
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！