题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回 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
思路
- 二叉搜索树最直观的性质就是: 当前节点的值大于左子树上任意节点的值, 并小于右子树上任意节点的值
- 所以我们可以利用这一性质, 采用类似二分迭代查找的方式来找后继者 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 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号