题目描述
判定一棵树是否满足二叉搜索树的性质。二叉查找树（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)
