作者：妞妞吃粑粑_577 | 来源：互联网 | 2023-09-18 18:36
给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
示例 2:
低级做法，中序遍历，看看是否是有序的
1 # Definition for a binary tree node.
2 # class TreeNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.left = None
6 # self.right = None
7
8 class Solution:
9 def isValidBST(self, root: TreeNode) -> bool:
10 res_ = []
11 stack = []
12 while root or stack:
13 if root:
14 stack.append(root)
15 root = root.left
16 else:
17 root = stack.pop()
18 res_.append(root.val)
19 root = root.right
20 stack=res_.copy()
21 stack.sort()
22 if len(set(stack)) != len(stack):
23 return False
24 return stack== res_
25
26
执行用时 :68 ms, 在所有 Python3 提交中击败了73.22%的用户
内存消耗 :16.8 MB, 在所有 Python3 提交中击败了7.23%的用户
每次将当前值和上下界进行比较，递归对其左右子树进行该过程：
1 class Solution:
2 def isValidBST(self, root):
3 """
4 :type root: TreeNode
5 :rtype: bool
6 """
7 def helper(node, lower = float(‘-inf‘), upper = float(‘inf‘)):
8 if not node:
9 return True
10
11 val = node.val
12 if val <= lower or val >= upper:
13 return False
14
15 if not helper(node.right, val, upper):
16 return False
17 if not helper(node.left, lower, val):
18 return False
19 return True
20
21 return helper(root)
执行用时 :76 ms, 在所有 Python3 提交中击败了42.48%的用户
内存消耗 :16.2 MB, 在所有 Python3 提交中击败了39.06%的用
LeetCode--098--验证搜索二叉树（python）
京公网安备 11010802041100号