【力扣刷题】验证二叉搜索树

98.验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

一开始拿到这道题以为很简单，就直接递归。但是递归有一些细节处理不好，比如：
①如何避免右子树存在比根节点小或者相等的节点；

②如何避免左子树存在比根节点大或者相等的节点；

刚开始尝试使用递归加上全局变量max来判断，无奈能力有限，以失败告终。先通过之后再在参考答案中学习。

后来就尝试迭代，通过中序遍历并对比结果与排序后的结果是否一致来达到验证的效果。虽然通过了测试用例，但是用时惨不忍睹。确实是缺乏经验，需要多刷题来弥补自身短板。

我的代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True     
        stack = []  # 中序遍历使用栈
        result = []  # 结果
        temp = root  # 当前节点

        while temp or stack:
            if temp != None:
                stack.append(temp)
                temp = temp.left

            else:
                temp = stack.pop()
                if temp.val not in result:
                    result.append(temp.val)
                else:
                    return False
                temp = temp.right

        compare = []
        for x in result:
            compare.append(x)
        result.sort()
        for i in range(len(result)):
            if compare[i] != result[i]:
                return False

        return True                    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

提交后学习了其他人的递归算法，也找到了自己一开始递归无法通过测试的原因，但全局变量这个想法是对的。使用递归后，执行用时明显缩短了。

递归代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        self.pre = -21474836480

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: 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

        return self.isValidBST(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26