Sui Xin's Blog

[LeetCode]98. 验证二叉搜索树（Validate Binary Search Tree）

Posted on In Disqus:

题目描述

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

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

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

示例 1:

输入:
2
/ \
1 3
输出: true

示例 2:

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

解题思路

  1. 解法一：递归。递归的判断整棵树的所有节点是否满足条件，必须保存此时该节点所在树的上界和下届。
  2. 解法二：迭代。使用 DFS 来实现解法一。
  3. 解法三：中序遍历。二叉搜索树的中序遍历序列为单调递增的序列。

代码

Python 3.6

解法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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.is_valid_core(root)
    
    def is_valid_core(self, node, lower=float("-inf"), upper=float("inf")):
        if node is None:
            return True
        if node.val >= upper or node.val <= lower:
            return False
        if not (self.is_valid_core(node.left, lower, node.val) and self.is_valid_core(node.right, node.val, upper)) :
            return False
        return True

执行用时 : 80 ms
内存消耗 : 16.2 MB

解法二：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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:
        stack = [(root, float("-inf"), float("inf"))]
        while stack:
            node, lower, upper = stack.pop()
            if node is None:
                continue
            if node.val >= upper or node.val <= lower:
                return False
            stack.append((node.left, lower, node.val))
            stack.append((node.right, node.val, upper))
        return True

执行用时 : 124 ms
内存消耗 : 16.2 MB

解法三：中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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:
        stack = []
        last = float("-inf")
        node = root
        while stack or node:
            while node is not None:
                stack.append(node)
                node = node.left
            node = stack.pop()
            if node.val <= last:
                return False
            last = node.val
            node = node.right
        return True

执行用时 : 120 ms
内存消耗 : 16.2 MB

参考

https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode/

Related Posts