程序员面试金典 - 面试题 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

题目思考

  1. 可以利用哪些性质来判断?
  2. 可以分别用迭代和递归实现吗?

解决方案

方案 1

思路

  • 二叉搜索树最直观的性质就是: 当前节点的值大于左子树上任意节点的值, 并小于右子树上任意节点的值
  • 所以我们可以利用这一性质, 采用类似二分迭代查找的方式来找后继者 res, 具体做法如下:
  • 首先初始化后继者 res 为 null, 代表 p 是最右节点, 没有后继者的情况
  • 然后从根节点开始遍历树, 可以分为以下两种情况:
    • 如果当前节点大于 p, 将 res 暂时置为当前节点, 然后尝试往左子树继续查找, 看看有没有更小的大于 p 的节点
    • 如果当前节点小于等于 p, 说明它不可能是后继者, 只能往右子树查找
  • 遍历结束后, 最后的 res 只能是 null 或者是最小的大于 p 的节点, 即后继者

复杂度

  • 时间复杂度 O(N): 每个节点只需要遍历一遍
  • 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        # 方法1: 利用二叉搜索树性质, 类似二分迭代查找
        cur = root
        res = None
        while cur:
            if cur.val > p.val:
                # 当前节点大于p, 将res暂时置为当前节点, 然后尝试往左子树继续查找, 看看有没有更小的大于p的节点
                res = cur
                cur = cur.left
            else:
                # 当前节点小于等于p, 只能往右子树查找
                cur = cur.right
        # 最终得到的res一定是大于p的最小节点或空节点(如果p最大)
        return res

方案 2

思路

  • 二叉搜索树还有另一个性质, 即中序遍历是有序的
  • 所以我们也可以利用这一性质, 引入额外参数 pre 来代表前一个节点, 并引入 res 表示最终所求的后继者
  • pre 需要初始化为 null, 因为最左节点前面没有节点; res 也要初始化为 null, 代表 p 是最右节点, 没有后继者的情况
  • 然后进行经典的递归中序遍历: 如果当前的 pre 节点恰好是 p, 那么当前节点自然就是后继者 res; 否则更新 pre 为当前节点的值, 用于之后的判断, 并继续中序遍历
  • 最后如果 res 已经找到了就可以直接终止递归, 做到剪枝优化

复杂度

  • 时间复杂度 O(N): 每个节点只需要遍历一遍
  • 空间复杂度 O(logN): 递归栈的消耗, 递归深度最多是树的高度, 也即 logN

代码

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
        # 方法2: 利用中序遍历性质
        # 中序遍历, 先找到p节点, 之后遍历到的第一个节点即为所求
        pre, res = None, None

        def inorder(node):
            nonlocal pre
            nonlocal res
            if not node or res:
                # 如果当前节点为空或已经找到了后继者, 直接返回
                return
            inorder(node.left)
            if pre == p:
                # 前一个节点是p, 当前节点node自然是后继者
                res = node
            pre = node
            inorder(node.right)

        inorder(root)
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

本文链接http://www.dzjqx.cn/news/show-617299.html