-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0098_Recursion.py
35 lines (32 loc) · 1.02 KB
/
Leetcode0098_Recursion.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 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 isValid(self, root):
if not root.left and not root.right:
return root.val, root.val, True
valid = True
minRoot = root.val
maxRoot = root.val
if root.left:
maxLeft, minLeft, ValidLeft = self.isValid(root.left)
minRoot = minLeft
if not ValidLeft or root.val<=maxLeft:
valid = False
if root.right:
maxRight, minRight, ValidRight = self.isValid(root.right)
maxRoot = maxRight
if not ValidRight or root.val>=minRight:
valid = False
return maxRoot, minRoot, valid
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
return self.isValid(root)[2]