描述
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
题目链接
思路
方法一：
递归遍历 + 利用对二叉搜索树进行中序遍历，得到的节点值是有序的这一特性，遍历一遍，然后判断数组是否有序即可。
方法二：
改进方法一，直接在遍历的过程中，判断出是否有序。但是要记录前一个节点值
方法一代码
class Solution:def __init__(self):self.result = []def traverse(self,root):if root == None:return self.traverse(root.left)self.result.append(root.val)self.traverse(root.right)def isValidBST(self , root: TreeNode) -> bool:#中序遍历self.traverse(root)# 检查数组是否升序 for i in range(len(self.result) -1):if self.result[i] > self.result[i+1]:return Falsereturn True
方法二代码
import sys
class Solution:def __init__(self):self.pre = -(sys.maxsize)def traverse(self,root):if root == None:return Trueif not self.traverse(root.left):return Falseif root.val < self.pre:return Falseself.pre = root.valif not self.traverse(root.right):return Falsereturn Truedef isValidBST(self , root: TreeNode) -> bool:return self.traverse(root)
骑车风好大，头给吹晕了
