python-leetcode 42.验证二叉搜索树

题目：

给定二叉树的根节点root,判断是否是一个有效二叉搜索树

有效二叉搜索树：

1.节点的左子树只包含小于当前节点的树

2.节点的右子树只包含大于当前节点的树

3.所有左子树和右子树自身必须也是二叉搜索树

方法一：递归

如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。

class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution(object):def isValidBST(self, root):def helper(node, lower=float('-inf'), upper=float('inf')):# 如果节点为空，说明已经遍历到叶子节点或空树，返回 Trueif not node:return Trueval = node.val# 当前节点的值必须大于 lower 且小于 upperif val <= lower or val >= upper:return False# 递归检查右子树，将当前节点的值作为新的 lowerif not helper(node.right, val, upper):return False# 递归检查左子树，将当前节点的值作为新的 upperif not helper(node.left, lower, val):return Falsereturn Truereturn helper(root)

时间复杂度：O(n)其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次

空间复杂度：O(n)

---

方法二：中序遍历

二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是

中序遍历是二叉树的一种遍历方式，它先遍历左子树，再遍历根节点，最后遍历右子树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isValidBST(self, root):""":type root: Optional[TreeNode]:rtype: bool"""stack=[]  #用于模拟递归的栈，用来存储待处理的节点inorder=float('-inf') #用于记录前一个访问的节点值。初始值为负无穷while stack or root: #栈不为空或者当前节点不为空while root:  #当前节点和所有左子树节点压入栈stack.append(root)root=root.leftroot=stack.pop()  #从栈中弹出一个节点
#之前压入的是当前节点和所有左子树节点，所以栈顶的节点是当前树的最左节点if root.val<=inorder:return Falseinorder=root.val #更新 inorder 为当前节点的值root=root.right #将当前节点的右子树作为下一个要处理的节点return True

时间复杂度：O(n)其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次

空间复杂度：O(n)

源自扣官方题解