两种写法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 思路:
# 1、中序遍历,将结果保存在ret中;
# 2、遍历ret,看是否是单增;
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
tmp = root
stack = []
ret = []
while tmp or stack:
while tmp:
stack.append(tmp)
tmp = tmp.left
node = stack.pop()
ret.append(node.val)
tmp = node.right
p1 = 0
p2 = 1
while p2 < len(ret):
if ret[p1] >= ret[p2]:
return False
p1 += 1
p2 += 1
return True
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
res = []
self.search(root, res)
for i in range(1,len(res)):
if res[i] <= res[i-1]:
return False
return True
def search(self, root, res):
if root:
self.search(root.left, res)
res.append(root.val)
self.search(root.right, res)