验证二叉搜索树

Leetcode Link: 98. 验证二叉搜索树 - 力扣（LeetCode）

题目

解法一

思路： 根据二叉搜索树的特点，可以发现通过中序遍历展开后，其数列应该是严格升序的

• 中序遍历展开二叉搜索树
• 判断展开后的数列是否严格升序 题解：

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        nums = []
        def dfs(node):
            if not node:
                return 
            dfs(node.left)
            nums.append(node.val)
            dfs(node.right)
            return 
        
        def check(nums):
            for i in range(1, len(nums)):
                if nums[i] <= nums[i-1]:
                    return False
            return True
 
        dfs(root) # 中序遍历展开
        return check(nums) # 判断是否严格升序

解法二

思路： 在解法一中，我们显式地利用中序遍历展开二叉树，这里我们思考能不能不显式展开呢？

可以看到，中序遍历的时候，我们向序列中添加新的数字的时候，该数字一定是下一个遇到的 node.val 在序列中的前一个元素。我们知道，中序遍历数列又是严格升序的，因此可以通过判断 node.val 和前一个数字的大小来避免显示展开序列 题解：

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        pre = -float('inf') # 保存中序遍历的前一个数字
        def dfs(node):
            nonlocal pre
            if not node:
                return True
            
            if not dfs(node.left): return False
            if node.val <= pre:  # 必需保证是严格升序的
                return False
            pre = node.val # 更新前一个数字
            if not dfs(node.right): return False
        
            return True
 
        return dfs(root)

启发和联系

二叉树的题目离不开三种遍历的方式。