[面试题 04.05][中等][DFS] 合法二叉搜索树

题目描述

面试题 04.05. 合法二叉搜索树

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:

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

示例 2:

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

解题思路

两种思路:

1. 检查当前节点的值, 是否比左子树的最大值大(或不小于该最大值, 我们认为相等的数, 应当放在左边), 比右子树的最小值小

2. 中序遍历整棵树, 得到的遍历序列必须是递增的, 才是二叉搜索树

下面的代码采用第一种思路.

# 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:
        def dfs(node):
            if node is None:
                return float('inf'), float('-inf')

            lmin, lmax = dfs(node.left)
            if lmin is False:
                return False, False
            rmin, rmax = dfs(node.right)
            if rmin is False:
                return False, False

            if node.val <= lmax or node.val >= rmin:
                return False, False
            return max(node.val, lmax), min(node.val, rmin)

        fmin, fmax = dfs(root)
        return True if fmin is not False else False