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)