LeetCode 题解

积跬步，至千里。

验证二叉搜索树

分类：LeetCode 标签： 树 深度优先搜索 发布于：2019-10-20 ID：98

题目描述

来源于 https://leetcode-cn.com/

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

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

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

示例 1:

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

示例 2:

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

解法：

首先想到的是根据二叉树的性质，即左子树中的值小于根节点的值，右子树中的值大于根节点的值。这样以来，对于每个节点，都有一个取值范围。比如某个左孩子的右孩子节点，它的值需要大于父节点，但要小于根节点。

    20
   /
 10
   \
    15

class Solution:
    def isValidBST(self, root):
        inf = float('inf')

        return self._isValidBST(root, max=inf, min=-inf)

    def _isValidBST(self, node, max, min):
        if not node:
            return True

        if not (min < node.val < max):
            return False

        if not self._isValidBST(node.left, min=min, max=node.val):
            return False

        if not self._isValidBST(node.right, min=node.val, max=max):
            return False
        
        return True

后来看别人提到一种更加巧妙的方法，一个二叉树查找树的中序遍历，是升序的。

class Solution:
    def isValidBST(self, root):
        stack = []
        node = root
        last = float('-inf')
        
        while stack or node:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()
            if last >= node.val:
                return False
            last = node.val
            
            node = node.right
        
        return True