[Leetcode][python]Validate Binary Search Tree

约定不等于承诺〃 2022-06-11 05:58 146阅读 0赞

## 题目大意 ##

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

## 解题思路 ##

想到了中序遍历整棵树，那么结果应该是升序的。直接套用之前的中序遍历代码，稍加修改即可。  
网上的答案很多都在分析负无穷正无穷（效率高？），我觉得能和之前中序遍历串起来就足够了。

## 代码 ##

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

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

### 中序遍历（无需生成数组） ###

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

## 总结 ##

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