98. 验证二叉搜索树 [medium]

https://leetcode-cn.com/problems/validate-binary-search-tree/

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

通过次数142,161 | 提交次数447,365

Second Try

2020-07-17

看题解才知道还有朴素的递归写法，不需要知道中序遍历的前置知识。

毕竟二叉搜索树的不同之处就是节点之间的有序，其大小被上游限制住了。只要在左侧的都比右侧的小，在右侧的都比左侧的大，并且这些大小能够合并传递下去，那么最后符合要求的就是二叉搜索树。

这个解法不错，思路清晰，代码简单。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        def check_bst(node, lower, upper):
            if not node:
                return True
            if lower >= node.val or node.val >= upper:
                return False 
            return check_bst(node.left, lower, node.val) \
                and check_bst(node.right, node.val, upper)
        
        return check_bst(root, float('-inf'), float('inf'))

执行用时：32 ms, 在所有 Python 提交中击败了84.24%的用户
内存消耗：17.3 MB, 在所有 Python 提交中击败了20.00%的用户

First Try

2020-07-17

要不是知道二叉搜索树的中序遍历是一个递增数列，还真是不知道该怎么写递归才行。

另外发现才几天没写，深度优先的中序遍历竟然没法毫无迟滞的写出来，在函数递归和stack=[root]之间犹豫了一会儿才摸索出快速的写法，还是有点不爽。前几天已经把三种深度优先写得快得飞起，才几天怎么又没感觉了。。。

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 直接中序遍历，看是否有序排列即可

        def dfs_inorder(root, rv):
            if root is None:
                return 
            dfs_inorder(root.left, rv)
            rv.append(root.val)
            dfs_inorder(root.right, rv)
        rv = []
        dfs_inorder(root, rv)
        # 也不能简单通过是否已经排序来判读，毕竟还不允许出现重复的。。。
        # return rv == sorted(rv) 
        for i in range(1, len(rv)):
            if rv[i] - rv[i-1] <= 0:
                return False 
        return True 

执行用时：52 ms, 在所有 Python 提交中击败了12.87%的用户
内存消耗：18.1 MB, 在所有 Python 提交中击败了20.00%的用户

failed try

一个失败的递归写法，只考虑到下游的左右两个节点，没考虑到全局的要求。

比如在root的右边的某个节点node，拥有子节点leftnode,有leftnode < node,但是 leftnode>root,这就出bug了。

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True 

        left = root.left 
        right = root.right 
        if left and left.val >= root.val:
            return False 
        if right and right.val <= root.val:
            return False 
        
        return self.isValidBST(left) and self.isValidBST(right)