题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
实现一个函数，检查一棵二叉树是否为二叉搜索树。
示例 1:
- 输入:
2 / \ 1 3
- 输出: true
示例 2:
- 输入:
5
/ \
1 4
/ \
3 6- 输出: false
- 解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
题目思考
- 可以利用二叉搜索树的哪些性质来判断?
解决方案
方案 1
思路
- 二叉搜索树最直观的性质就是: 当前节点的值大于左子树上任意节点的值, 并小于右子树上任意节点的值
- 所以我们可以利用这一性质, 引入当前树的上下界来递归判断
- 如果当前根节点的值在上下界范围内, 则递归判断左右子树, 同时更新左子树的上界和右子树的下界为当前节点的值; 否则说明不是合法的二叉搜索树, 返回 false
- 另外注意初始化时上下界是-inf 和+inf, 表示整个树的根节点可以取任何值
复杂度
- 时间复杂度 O(N): 每个节点只需要遍历一遍
- 空间复杂度 O(logN): 递归栈的消耗, 递归深度最多是树的高度, 也即 logN
代码
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
# 方法1: 加入上下界递归判断
def check(node, mn, mx):
# mn和mx表示当前子树的上下界取值范围, 即子树内的所有节点的值都要在(mn, mx)之间
if not node:
return True
if not mn < node.val < mx:
# 当前节点不属于该范围内, 说明不是合法的二叉搜索树
return False
# 检查左右子树, 注意上下界也要更新
# 即左子树的mx和右子树的mn要更新为当前节点值
return check(node.left, mn, node.val) & check(
node.right, node.val, mx)
# 初始化的上下界自然是-inf和+inf
return check(root, -float('inf'), float('inf')) 方案 2
思路
- 二叉搜索树还有另一个性质, 即中序遍历是有序的
- 所以我们也可以利用这一性质, 引入额外参数 pre 来代表前一个节点的值, 并引入一个 valid 布尔值表示是否合法
- 然后中序遍历并比较 pre 和当前节点 cur 的值: 如果 pre 大于等于它的话则说明不是合法的二叉搜索树, 将 valid 置为 false; 否则更新 pre 为当前节点的值, 用于之后的判断, 并继续中序遍历
- 另外注意初始化时 pre 是-inf, 表示整个树的最小节点可以取任何值
复杂度
- 时间复杂度 O(N): 每个节点只需要遍历一遍
- 空间复杂度 O(logN): 递归栈的消耗, 递归深度最多是树的高度, 也即 logN
代码
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
# 方法2: 中序遍历, 引入额外参数pre表示上一个元素的值
pre = -float('inf')
valid = True
def inorder(node):
nonlocal pre
nonlocal valid
if not node or not valid:
# 如果节点为空或者已经不是合法二叉搜索树了, 直接退出
return
inorder(node.left)
if pre >= node.val:
# 前一个值大于等于当前值, 不满足二叉搜索树的要求, 无效
valid = False
return
# 不要忘了更新前一个值为当前值, 用于下一次判断
pre = node.val
inorder(node.right)
inorder(root)
return valid 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号