目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

二、解题思路

思路是：

左子树小于其父亲但大于其爷爷：root是左子树，min是爷爷，max是父亲

右子树大于其父亲但小于其爷爷：root是右子树，min是父亲，max是爷爷

三、代码

      # Definition for a binary tree node.
      class TreeNode:
      def __init__(self, x):
       self.val = x
       self.left = None
       self.right = None
      class Solution:
      def isValidBST(self, root: TreeNode) -> bool:
      if root is None:
      return True
      def dfs(root, min, max):
      if min is not None and root.val <= min:
      return False
      if max is not None and root.val >= max:
      return False
      if root.left:
      if root.val <= root.left.val:
      return False
      if not dfs(root.left, min, root.val):
      return False
      if root.right:
      if root.val >= root.right.val:
      return False
      if not dfs(root.right, root.val, max):
      return False
      return True
      return dfs(root, None, None)
      if __name__ == '__main__':
       a = TreeNode(5)
       a.left = TreeNode(1)
       a.right = TreeNode(6)
       a.right.left = TreeNode(3)
       a.right.right = TreeNode(7)
      # a = TreeNode(10)
      # a.left = TreeNode(5)
      # a.right = TreeNode(15)
      # a.right.left = TreeNode(6)
      # a.right.right = TreeNode(20)
       s = Solution()
       ans = s.isValidBST(a)
       print(ans)
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108718330