98. 验证二叉搜索树

Difficulty
Medium
Tags
二叉树
二叉搜索树
URL
https://leetcode-cn.com/problems/validate-binary-search-tree/
Star
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
    2
   / \
  1   3
输出: true
示例 2:
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

分析

简单比较每个节点的左右子节点显然是不行的，要求的是某节点所有的左子节点都要小于该节点。如下图，就不是搜索二叉树。
notion imagenotion image

法1 递归 + 中序遍历

思路
采用中序遍历，因为中序遍历天然的是左中右这样一个顺序，如果是搜索二叉树，中序遍历得到的将是递增的列表。
所以有如下两种策略：
  • 边遍历边比较：维护一个最小值，一直边遍历边更新这个最小值，当遇到比这个最小值还小的值，说明不满足搜索二叉树。
  • 先遍历一遍将节点值保存，再判断保存的列表是否为升序。
题解
策略1
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.minVal = float('-inf') # 用来表示最小的数字
    def isValidBST(self, root: TreeNode) -> bool:
        # 基线条件
        if root is None:
            return True
        # 单层递归的逻辑
        left = self.isValidBST(root.left)
        if self.minVal < root.val:
            self.minVal = root.val
        else:
            return False
        right = self.isValidBST(root.right)
        # 返回
        return left and right
上述方法采用了比较最小值的策略，其实可以保留上一个值，然后和当前值比较，因为二叉搜索树的中序遍历是个递增序列
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.pre = None

    def isValidBST(self, root: TreeNode) -> bool:
        if root is None:
            return None
        return self.dfs(node=root)

    def dfs(self, node):
        if node is None:
            return True
        
        left = self.dfs(node.left)
        # 剪枝操作
        if left == False:
            return left
        if self.pre and self.pre.val >= node.val:
            return False
        self.pre = node

        right = self.dfs(node.right)
        return right and left
策略2 垃圾！
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.result = [] # 用来保存节点值
    def isValidBST(self, root: TreeNode) -> bool:
        self.traversal(root)
        return sorted(self.result) == self.result or\
               sorted(self.result, reverse=True) == self.result

    def traversal(self, root:TreeNode):
        # 基线条件
        if root is None:
            return
        # 单层递归的逻辑
        self.isValidBST(root.left)
        self.result.append(root.val)
        self.isValidBST(root.right)

法2 递归+前序遍历

思路
对如下二叉树，每个节点值的范围如括号所示,递归的时候，不断修改范围区间即可
notion imagenotion image
故可总结规律：
定义 min, max 为递归函数参数
对每个节点需满足 min < node < max
对该节点左子树满足 min <node.left <node
对该节点右子树满足 node <node.left <max
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.preOrder(node=root, min_=-float('inf'), max_=float('inf'))

    def preOrder(self, node, min_, max_):
        if node is None:
            return True
        if node.val >= max_ or node.val <= min_:
            return False
        
        left = self.preOrder(node.left, min_=min_, max_=node.val)
        right =  self.preOrder(node.right, min_=node.val, max_ = max_) 
        return left and right
进行剪肢优化，提前返回不满足的条件
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.preOrder(node=root, min_=-float('inf'), max_=float('inf'))

    def preOrder(self, node, min_, max_):
        if node is None:
            return True
        if node.val >= max_ or node.val <= min_:
            return False
        
        left = self.preOrder(node.left, min_=min_, max_=node.val)
        if left == False:
            return left
        return self.preOrder(node.right, min_=node.val, max_ = max_)

法3 迭代法

思路
同递归法一样。只是换做了迭代来遍历二叉树
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        minVal = float('-inf') # 用来表示最小的数字
        stack = []
        cur = root
        while len(stack) > 0 or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                if minVal >= cur.val:
                    return False
                else:
                    minVal = cur.val
                cur = cur.right
        return True