#98 Validate Binary Search Tree——Top 100 Liked Questions

港控/mmm° 2022-01-23 06:34 162阅读 0赞

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

Assume a 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:**

2
       / \
      1   3
    
    Input: [2,1,3]
    Output: true

**Example 2:**

5
       / \
      1   4
         / \
        3   6
    
    Input: [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.

> 第一次：递归能看懂却写不出来
> 
>     # 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 helper(node, lower, upper):
>                 
>                 if not node:
>                     return True
>                 if lower is not None and node.val <= lower:
>                     return False
>                 if upper is not None and node.val >= upper:
>                     return False
>                 return helper(node.left, lower, node.val) and helper(node.right, node.val, upper)
>             return helper(root, None, None)
> 
> Runtime: 40 ms, faster than 59.51% of Python online submissions forValidate Binary Search Tree.
> 
> Memory Usage: 16.4 MB, less than 62.68% of Python online submissions for Validate Binary Search Tree