# 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: Optional[TreeNode]) -> bool:
# 思路是把这棵树中序遍历一遍,看是否是升序数组
def myfunc(root,res):
if not root:
return None
myfunc(root.left,res)
res.append(root.val)
myfunc(root.right,res)
treeToarray=[]
myfunc(root,treeToarray)
# 判断一个数组是不是升序,从前往后遍历数组,相减,如果有正数,说明这个数组不是升序
i=0
while i<len(treeToarray)-1:
treeToarray[i]=treeToarray[i]-treeToarray[i+1]
if treeToarray[i]>=0:
return False
i=i+1
return True
思路:
从二叉搜索树的来源思考本题:二叉搜索树就是来自一个有序数组,从中间来一个入口,这样就使用二分法加快查找效率
这样还不够快,那么为什么不再对左右两个数组进行二分呢,所以就有了下图:
把中间这个4节点拎起来,就是一颗二叉搜索树
那么这道题就是使用了逆方法:二叉搜索树的中序遍历是一个升序数组
然后为了不增加复杂度,在原数组上前减后,如果有正数,说明这个数组不是升序数组