验证二叉搜索树——题解
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
因此：我们发现如果中序遍历二叉树，将递增的结果保存在数组中，如果该数组是一个递增序列，那就是一个有效的二叉搜索树。
# 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
腾讯云智研发二面50人在聊
查看3道真题和解析