What makes a binary tree a valid Binary Search Tree?

A Binary Search Tree is valid if, for every node, its left child contains values smaller than the node and the right child contains values greater, with this property recursively applying to every node in the tree.

How does the recursive approach work to validate a BST?

In the recursive approach, each node’s value is validated by ensuring it falls within a valid range that is updated as we traverse down the tree. The left child should be smaller, and the right child should be larger.

What is the time complexity of this problem?

The time complexity is O(N), where N is the number of nodes in the tree, since each node is visited once during the DFS traversal.

Can this solution handle edge cases like empty or single-node trees?

Yes, the solution works for edge cases like an empty tree or a single node. In these cases, the tree is automatically considered valid.

How do you handle unbalanced trees in this problem?

The solution handles unbalanced trees effectively by ensuring that each node’s left and right children respect the required bounds, regardless of the tree's structure.

#98

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：节点的左子树只包含严格小于当前节点的数。节点的右子树只包含严格大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1：输入： root = [2,1,3] 输出： t…

树深度优先搜索二叉搜索树二叉树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 10⁴] 内
-2³¹ <= Node.val <= 2³¹ - 1

lightbulb

解题思路

方法一：递归

我们可以对二叉树进行递归中序遍历，如果遍历到的结果是严格升序的，那么这棵树就是一个二叉搜索树。

因此，我们使用一个变量 $\textit{prev}$ 来保存上一个遍历到的节点，初始时 $\textit{prev} = -\infty$ ，然后我们递归遍历左子树，如果左子树不是二叉搜索树，直接返回 $\textit{False}$ ，否则判断当前节点的值是否大于 $\textit{prev}$ ，如果不是，返回 $\textit{False}$ ，否则更新 $\textit{prev}$ 为当前节点的值，然后递归遍历右子树。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点个数。

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, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(root: Optional[TreeNode]) -> bool:
            if root is None:
                return True
            if not dfs(root.left):
                return False
            nonlocal prev
            if prev >= root.val:
                return False
            prev = root.val
            return dfs(root.right)

        prev = -inf
        return dfs(root)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand the properties of a valid Binary Search Tree?
question_mark
Can you explain how recursion helps track valid ranges for nodes?
question_mark
Will you describe the time and space complexity of this solution?

warning

常见陷阱

外企场景

error
Not correctly maintaining the range for each node during recursion.
error
Misunderstanding how the left and right subtrees' valid ranges differ.
error
Failing to account for edge cases like a tree with only one node.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if a binary tree is a valid AVL tree (self-balancing binary search tree).
arrow_right_alt
Determine if a binary tree is a valid Binary Search Tree with duplicate values allowed.
arrow_right_alt
Validate a Binary Search Tree using iterative traversal techniques.

help

常见问题

外企场景

继续练习

#99 恢复二叉搜索树 #230 二叉搜索树中第 K 小的元素 #235 二叉搜索树的最近公共祖先