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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
import sys

class Solution:
    pre = -sys.maxsize - 1
    # def isValidBST(self , root: TreeNode) -> bool:
    #     # write code here
    #     """method_1: 递归实现
    #     思路：中序递归遍历，
    #     步骤：
    #     step1: 递归到最左，初始化maxLeft和pre
    #     step2: 往后遍历整棵树， 依次连接pre与当前节点，并更新pre；
    #     step3: 左子树如果不是二叉搜索树返回false
    #     step4: 判断当前节点是不是小于前置节点，更新前置节点。
    #     step5: 最后由右子树后面节点决定。
    #     """
    #     if not root:
    #         return True
    #     # left tree
    #     if not self.isValidBST(root.left):
    #         return False
    #     if root.val <= self.pre:
    #         return False
    #     # update current value
    #     self.pre = root.val
    #     # enter right tree
    #     if not self.isValidBST(root.right):
    #         return False
    #     return True

    def isValidBST(self, root: TreeNode) -> bool:
        """ 
        method_2: 非递归思路
        思路： 使用栈代替递归。 每次访问最左元素不止对二叉树成立，而是对所有子问题都成立，循环时最开始都是遍历最左
        步骤：
        step1: 判断树空，空树不遍历；
        step2: 准备数组记录中序遍历的结果；
        step3: 准备辅助栈，当二叉树节点为空了且栈中没有节点，就停止访问；
        step4: 从根节点开始，每次优化进入每棵子树的最左边节点，将其不断加入栈中，用来保存父问题；
        step5. 到达最左后，可一开始访问，如果还有右节点，则将右边也加入栈中，之后右子树的访问也是有先导最左；
        step6: 遍历数组，依次比较相邻两个元素是否为递增序
        """
        tmp_stack, sort_list = list(), list()

        head = root
        while head or tmp_stack:
            while head:
                tmp_stack.append(head)
                head = head.left
            head = tmp_stack[-1]

            tmp_stack.pop()
            sort_list.append(head.val)
            head = head.right
        for i in range(1, len(sort_list)):
            if sort_list[i - 1] > sort_list[i]:
                return False

        return True
        
        pass

        pass
		假笑王子