LC 面试题 04.06. 后继者

题目描述

这是 LeetCode 上的 面试题 04.06. 后继者 ，难度为 中等。

设计一个算法，找出二叉搜索树中指定节点的 “下一个” 节点（也即中序后继）。

如果指定节点没有对应的 “下一个” 节点，则返回 null。

示例 1:

输入: root = [2,1,3], p = 1

  2
 / \
1   3

输出: 2

示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null

---

BST 特性 + 递归

利用 BST 的特性，我们可以根据当前节点 root 与 p 的值大小关系来确定搜索方向：

1. 若有 root.val <= p.val : 根据 BST 特性可知当前节点 root 及其左子树子节点均满足「值小于等于 p.val」，因此不可能是 p 点的后继，我们直接到 root 的右子树搜索 p 的后继（递归处理）；
2. 若有 root.val > p.val : 当第一次搜索到满足此条件的节点时，在以 root 为根节点的子树中「位于最左下方」的值为 p 的后继，但也有可能 root 没有左子树，因此 p 的后继要么在 root 的左子树中（若有），要么是 root 本身，此时我们可以直接到 root 的左子树搜索，若搜索结果为空返回 root，否则返回搜索结果。

代码：

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;
        if (root.val <= p.val) return inorderSuccessor(root.right, p);
        TreeNode ans = inorderSuccessor(root.left, p);
        return ans == null ? root : ans;
    }
}

• 时间复杂度：复杂度与深度相关，最坏情况下仍会搜索所有节点，复杂度为 $O(n)$
• 空间复杂度：忽略递归带来的额外空间消耗，复杂度为 $O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.面试题 04.06 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。