LeetCode

Appearance

98. Validate Binary Search Tree ​

题目 ​

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

 

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1
Related Topics
  • 树
  • 深度优先搜索
  • 二叉搜索树
  • 二叉树

  • 👍 2599
  • 👎 0

    • 思路 ​

    搜索二叉树的每一个节点都有一个节点范围

    • min < 左子树的节点 < root.val
    • root.val < 右子树节点 < max

    其中 python 中最大值是 float('-inf'), 最大值 float('inf')

    解法 ​

    python
    class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def isValid(root, min, max):
            if not root:
                return True

            if min < root.val < max:
                return isValid(root.left, min, root.val) and isValid(root.right, root.val, max)
            else:
                return False


        return isValid(root, float('-inf'), float('inf'))

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)

    解法二 ​

    二叉树中序遍历的结果是一个递增序列的，可判定为是一颗二叉搜索树

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:

        self.predecessor = float('-inf')

        def dfs(root):
            if not root:
                return True

            if root.left and not dfs(root.left):
                return False

            if root.val > self.predecessor:
                self.predecessor = root.val
            else:
                return False

            if root.right and not dfs(root.right):
                return False

            return True


        return dfs(root)
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)