動機
當初還想著怎麼看node…
Problem
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: falseExplanation: 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
Sol
直接把範圍傳下去就好了
class Solution:
def isValidBST(self, root: TreeNode,l=float('-inf'),r=float('inf')) -> bool:
if not root:
return True
elif root.val <= l or r <= root.val:
return False
else:
return self.isValidBST(root.left, l, root.val) and self.isValidBST(root.right, root.val, r)