树-98. 验证二叉搜索树-PYTHON

Georgia ·

更新时间:2024-11-10

· 945 次阅读

在这里插入图片描述

递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def helper(node,lower = float("-inf"),upper = float("inf")):
            if not node:
                return True #递归结束条件
            val = node.val
            if val = upper:  #如果触犯了搜索树的原则直接返回False
                return False
            if not helper(node.right,val,upper): #判断右子树是否都大于当前节点值
                return False
            if not helper(node.left,lower,val): #判断左子树是否都小于当前节点值
                return False
            return True  #如果都通过了就代表没问题
        return helper(root)

迭代

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True   #树为空
        stack = [(root,float("-inf"),float("inf")),]
        while stack:
            root,lower,upper = stack.pop()
            if not root:
                continue
            val = root.val
            if val = upper:
                return False
            stack.append((root.right,val,upper))  #向栈中填充右子树数据
            stack.append((root.left,lower,val))   #向栈中填充左子树数据
        return True

中序遍历

在这里插入图片描述

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack,inorder = [],float("-inf")
        while stack or root:
            while root:
                stack.append(root)#将根节点和所有左子树存储在栈内
                root = root.left
            root = stack.pop()
            if root.val <= inorder: #因为预测是一个元素递增的关系，如果存在下一个元素小于上一个那么就返回失败
                return False
            inorder = root.val #将当前值设为最小，用于和下一个元素比较
            root = root.right #有右子树的情况
        return True

作者：宋建国

二叉搜索树 Python

1024 个赞