Leetcode 98 验证二叉搜索树

Time: 2019-08-10

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:

    2
   / \
  1   3

输出: true
示例 2:

输入:

    5
   / \
  1   4
     / \
    3   6

输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

按照BST的特征来进行筛选过滤。注意BST是当前结点要比全部的左子树的元素要大，比全部的右子树的元素要小，所以上下边界并不是临近结点。

代码

标准的模板写法：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.dfs(root)
    
    def dfs(self, node, lower=float('-inf'), upper=float('inf')):
        # 递归出口
        if not node:
            return True
        val = node.val
        # 若当前结点值小于等于左边界或者大于等于右边界，则不是BST
        if val <= lower or val >= upper:
            return False
        # 递归拆解
        # 向右子树，则当前结点值是下界
        if not self.dfs(node.right, val, upper):
            return False
        # 向左子树，当前结点值是上界
        if not self.dfs(node.left, lower, val):
            return False
        return True

时空复杂度

时间复杂度：O(n)

相似题目

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

END.