题解 | 判断是不是二叉搜索树 参考题解

import sys
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
import math
class Solution:
    """
    {3,2,5,1,4} 报错会返回true

          3 
         / \
         2  5
            /\
            1 4 
     二叉搜索树 需要  左子树 全部 < 根 < 右子树全部
     需要使用中序递归 中序是递增序列


    """
    def isValidBST_error(self , root: TreeNode) -> bool:
        # write code here
        def  dfs(root):
            if not root:
                return True
            if not  root.left and not root.right:
                return True 
            if root.left and root.right:
                if root.left.val<root.val and  root.right.val>root.val:
                    return dfs(root.left) and dfs(root.right)
                else:
                    return False
            else:
                return False 
        return dfs(root)
    def isValidBST_1(self , root: TreeNode) -> bool:
        
        def dfs(root,min_val,max_val):
            # 节点为空
            if not root:
                return True
            # 值不满足要求
            if  root.val <=min_val or root.val >=max_val:
                return False 
            return dfs(root.left ,min_val,root.val ) and dfs(root.right,root.val,max_val)
        #return dfs(root ,-inf,inf ) # 在牛客 导入 import math 会报错
        return dfs(root ,-2**32,2**31  )
    import sys
    # 中序遍历方法: https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b?tpId=295&tqId=2288088&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    # pre =-sys.maxsize-1
    # def isValidBST_2(self , root: TreeNode) -> bool:
        
    #     # 如果节点为空直接返回
    #     if not root: 
    #         return True 
    #     # 遍历左子树 --最左侧开始 
    #     if not  self.isValidBST( root.left):
    #         return False 
    #     # 判断值
    #     if root.val<self.pre:
    #         return False 
    #     # 更新最小值
    #     self.pre=root.val 
    #     # 遍历右子树
    #     if not self.isValidBST(root.right):
    #         return False
    #     return True 
    def isValidBST(self , root: TreeNode) -> bool:
        """
          栈使用 
          直到没有左节点
          while（head!=null）
             s.push(head)
             head=head.left
          然后进入右子树
         
         实现步骤： 
         1. 定义一个stack 保存访问的节点
         2. 定义一个数组arr保存中序遍历的val 
         3.  root 指向不为空 ，栈stack 不为空
             3.1循环遍历到最左侧压栈
             3.2 取出栈stack 栈顶
             3.3 将栈顶的值加入arr
             3.4 进入右边 root=root.right
        4. 遍历中序结果 arr 如果出现降序则不是搜索树


        """
        st=[]
        arr=[]

        while st or root:
            #压栈
            while root:
                st.append(root)
                root=root.left 
            root=st.pop()
            arr.append(root.val)
            root=root.right
        for i in range(1,len(arr)):
            if (arr[i-1]>arr[i]):
                return False
        
        return True