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

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

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

示例 1:

  1. 输入:
  2.     2
  3.    / \
  4.   1   3
  5. 输出: true

示例 2:

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

题解

递归很好理解，就是遍历整个二叉搜索树，比较该节点的值与左右子树节点值是否满足二叉搜索树的定义即可

递归

Python

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def helper(self,node,left,right):
  9.         if not node:
  10.             return True
  11.         if node.val <= left or node.val >= right:
  12.             return False
  13.         return self.helper(node.left,left,node.val) and self.helper(node.right,node.val,right)
  14.     def isValidBST(self, root: TreeNode) -> bool:
  15.         return self.helper(root,float('-inf'),float('inf'))

JavaScript

const helper = (root, lower, upper) => {
    if (root === null) {
        return true;
    }
    if (root.val <= lower || root.val >= upper) {
        return false;
    }
    return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
}
var isValidBST = function(root) {
    return helper(root, -Infinity, Infinity);
};

复杂度分析

  • 时间复杂度 : 🥈 98. 验证二叉搜索树 - 图1，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 🥈 98. 验证二叉搜索树 - 图2
  • 空间复杂度 : 🥈 98. 验证二叉搜索树 - 图3，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 🥈 98. 验证二叉搜索树 - 图4。

中序遍历

因为二叉搜索树中序遍历的结果是一个升序的序列，所以在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可

递归的中序遍历

# 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:
        ans=[]
        def inorder(node):
            if not node:
                return 
            inorder(node.left)
            ans.append(node.val)
            inorder(node.right)
        inorder(root)
        for i in range(1,len(ans)):
            if ans[i]<=ans[i-1]:
                return False
        return True

非递归的中序遍历

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack, inorder = [], float('-inf')

        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right

        return True