蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Validate Binary Search Tree

发表于 更新于 分类于 阅读次数： Valine：

题目大意

判断一棵树是否为二叉搜索树

解题思路

想到了中序遍历整棵树，那么结果应该是升序的。直接套用之前的中序遍历代码，稍加修改即可。

网上的答案很多都在分析负无穷正无穷（效率高？），我觉得能和之前中序遍历串起来就足够了。

代码

中序遍历（生成数组后判断是否为升序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def inorderTraversal(self, root, inorder):
        if root:
            self.inorderTraversal(root.left, inorder)
            inorder.append(root.val)
            self.inorderTraversal(root.right, inorder)
        
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        # if not root.left or not root.right:
        #     return True
        inorder = []
        self.inorderTraversal(root, inorder)
        for i in range(len(inorder)-1):
            if inorder[i] >= inorder[i+1]:
                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
class Solution(object):
    flag = True
    pre = -2147483649  # 有一个测试集是-2147483648
    def inorderTraversal(self, root):
        if root:
            self.inorderTraversal(root.left)
            # print self.flag, self.pre, root.val
            if self.pre >= root.val:
                self.flag = False
            self.pre = root.val
            # print self.flag, self.pre, root.val,'2'
            self.inorderTraversal(root.right)
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        # if not root.left or not root.right:
        #     return True
        self.inorderTraversal(root)
        return self.flag

总结

二叉搜索树和中序遍历关系密切