Jianbo Dai's

mq039.验证二叉搜索树

 
  • Dec 08, 2020

题目链接

先是自己写了一下，emmm写的是考察临接的左右子节点是否满足条件，并没有保证整棵子树。要保证正确的话在递归的时候要传递相应的上下界才行。递归的话时间复杂度是O（N），空间复杂度是O（N）。除了递归之外还有一种做法就是利用二叉搜索树的中序遍历能产生一个严格递增的数组的性质，如2所示。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST1(self, root: TreeNode) -> bool:

        def recursion(node, lower=float("-inf"), upper=float("inf")):
            if not node:
                return True
            value = node.val
            if value >= upper or value <= lower:
                return False
            return recursion(node.left, lower, node.val) and recursion(node.right, node.val, upper)

        return recursion(root)

    def isValidBST2(self, root):
        stack, inorder = [], float('-inf')
        
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right

        return True
Search