Leetcode-Medium 98. Validate Binary Search Tree
Leetcode-Medium 98. Validate Binary Search Tree
题目描述
判定一棵树是否满足二叉搜索树的性质。二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
思路
下面是看到的一个大佬的思路讲解，非常清楚了，原文在：https://leetcode.com/problems/validate-binary-search-tree/discuss/158094/Python-or-Min-Max-tm Python | 给你把Min Max来由说透 - 公瑾™
> 类型：DFS遍历
> Time Complexity O(n)
> Space Complexity O(h)LC里面各种花式炫技巧，炫答案，但没看到正儿八经给初学者解释关于Min Max运用的原理，这里公瑾给大家带来一个我最先犯的错误，然后是如何改进的。
错误代码(Buggy Code)
class Solution(object):
def isValidBST(self, root):
return self.helper(root)
def helper(self, node):
if not node: return True
if node.left and node.left.val >= node.val:
return False
if node.right and node.right.val <= node.val:
return False
left = self.helper(node.left)
right = self.helper(node.right)
return left and right上面代码看起来好像也没什么毛病，但以下这种情况是过不了的
5
/ \
1 4
/ \
3 6为什么？因为我们每层在当前的root分别做了两件事情：
- 检查
root.left.val是否比当前root.val小 - 检查
root.right.val是否比当前root.val大
大家可以用这个思路过一下上面这个例子，完全没问题。 那么问题来了，Binary Search Tree还有一个定义，就是
- 左边所有的孩子的大小一定要比
root.val小 - 右边所有的孩子的大小一定要比
root.val大
我们错就错在底层的3，比顶层的5，要小。
ok，概念弄懂了，如何解决这个问题呢？我们可以从顶层开始传递一个区间，举个例子。 在顶层5，向下传递的时候， 他向告诉左边一个信息： 左孩子，你和你的孩子，和你孩子的孩子，孩子的...........孩子都不能比我大哟 他向告诉右边一个信息： 右孩子，你和你的孩子，和你孩子的孩子，孩子的...........孩子都不能比我小哟
所以5告诉左边1的信息/区间是：(-infinite, 5) 所以5告诉右边4的信息/区间是：(5 , infinite)
然后我们要做的就是把这些信息带入到我们的代码里，我们把区间的左边取名lower_bound, 右边取名upper_bound
这样才有了LC被复制到烂的标准答案
class Solution(object):
def isValidBST(self, root):
return self.helper(root, -float('inf'), float('inf'))
def helper(self, node, lower_bound, upper_bound):
if not node: return True
if node.val >= upper_bound or node.val <= lower_bound:
return False
left = self.helper(node.left, lower_bound, node.val)
right = self.helper(node.right, node.val, upper_bound)
return left and right这题呢，还有另外一个根据BST性质进行Inorder操作的答案
暴力解法：
利用数组储存inorder过的数，如果出现重复，或者数组不等于sorted(arr)，证明不是Valid Tree
这个解法比较易读，如果对Space Complexity要求不严格，可以通过比对数组里面的数而不是sorted(arr)来达到O(N)时间复杂。
class Solution(object):
def isValidBST(self, root):
self.arr = []
self.inorder(root)
return self.arr == sorted(self.arr) and len(self.arr) == len(set(self.arr))
def inorder(self, root):
if not root: return
self.inorder(root.left)
self.arr.append(root.val)
self.inorder(root.right)O(1) Space解法：
在上面的算法里进行了优化，每次只需要将当前root.val和上次储存的self.last比对即可知道是否满足条件。然后设立self.flag用于返回。
class Solution(object):
def isValidBST(self, root):
self.last = -float('inf')
self.flag = True
self.inorder(root)
return self.flag
def inorder(self, root):
if not root: return
self.inorder(root.left)
if self.last >= root.val:
self.flag = False
self.last = root.val
self.inorder(root.right)腾讯云开发者
