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.
Input: root = [2,1,3] Output: true
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.
- The number of nodes in the tree is in the range
-231 <= Node.val <= 231 - 1
A tree is a valid binary search tree when if its left subtree and right subtree are both valid binary search trees and its root value greater than the max value of the left subtree and its root value is less than the minimum value of the right subtree.
# 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: TreeNode) -> bool: return self.helper(root, sys.maxsize, -sys.maxsize) def helper(self, root, max_value, min_value): if not root: return True left = self.helper(root.left, root.val, min_value) right = self.helper(root.right, max_value, root.val) return left and right and root.val < max_value and root.val > min_value
- Time complexity: O(N).
- Space complexity: O(N).