Leetcode-98. 验证二叉搜索树
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
解法:
分为两种,第一种是进行中序的遍历(左中右顺序遍历),如果得到的数组是升序的,那么就是二叉搜索树;第二种是使用递归,验证左子树是二叉排序树的时候找出最大值,验证右子树是二叉排序树的时候找出最小值,如果根节点满足大于左子树最大值,小于右子树最小值,则是二叉排序树。
时间复杂度:由于每个节点仅被访问一次,所以时间复杂度是O(N)
- Java
注意使用Integer类是因为要传入null,int类型不可为null
同时因为java不能返回多个值,将min,max作为函数参数进行迭代返回
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
public boolean isValidBST(TreeNode root) {
return this.isValid(root,null,null);
}
public boolean isValid(TreeNode root,Integer min,Integer max){
// 这里使用了包装类
if(root==null) return true;
if(max!=null && root.val>=max) return false;
if(min!=null && root.val<=min) return false;
return this.isValid(root.left,min,root.val) && this.isValid(root.right,root.val,max);
}
}
- Python
class Solution:
def isValidBST(self, root):
def isValid(root, min = float('-inf'), max = float('inf')):
if not root: return True
if root.val <= min or root.val >= max:
return False
if not isValid(root.right, root.val, max):
return False
if not isValid(root.left, min, root.val):
return False
return True
return isValid(root)
使用中序遍历,一种很优雅的写法,可惜效率和空间利用都很低
使用set是防止出现左右子树中有与根节点相同大小的值,导致返回了True
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
lst = self.inOrder(root)
print(lst)
return lst==list(sorted(set(lst)))
def inOrder(self,root):
if not root: return []
return self.inOrder(root.left) + [root.val] + self.inOrder(root.right)