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)