目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

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

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

示例 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