给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
因此:我们发现如果中序遍历二叉树,将递增的结果保存在数组中,如果该数组是一个递增序列,那就是一个有效的二叉搜索树。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def __init__(self): self.myqueue = [] def isValidBST(self, root: TreeNode) -> bool: if not root : return True self.helper(root) return self.isIncrease() def helper(self, root: TreeNode): if root.left: self.helper(root.left) self.myqueue.append(root.val) if root.right: self.helper(root.right) def isIncrease(self): pre = self.myqueue[0] for i in range(1, len(self.myqueue)): if pre >= self.myqueue[i]: return False pre = self.myqueue[i] return True