Python示例
# Python示例
核心是通过全部变量 pre
记录前节点的值
class Solution:
pre = float('-inf')
def isValidBST(self, root: TreeNode) -> bool:
if not root: return True
if not self.isValidBST(root.left): # 如果左子树不符合,就返回否
return False
if root.val <= self.pre: # 比前面的小,或者相等
return False
self.pre = root.val
if not self.isValidBST(root.right):
return False
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
本质上就是 中序遍历,下面改成中序遍历的版本。
class Solution:
res = True
pre = float('-inf')
def isValidBST(self, root: TreeNode) -> bool:
def midorder(root):
if not self.res: return
if not root: return
midorder(root.left)
if root.val <= self.pre:
self.res = False
self.pre = root.val
midorder(root.right)
if not root: return self.res
midorder(root)
return self.res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54