leetcode
leetcode 51 ~ 100
验证二叉搜索树

验证二叉搜索树

难度:

标签:

题目描述

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

代码结果

运行时间: 56 ms, 内存: 18 MB

/*
 * 使用Java Stream判断二叉树是否为有效的二叉搜索树。
 * 思路：
 * 1. 使用中序遍历获得节点值的列表，若是二叉搜索树，该列表应为严格递增。
 * 2. 使用Stream API遍历树，检查是否满足二叉搜索树的条件。
 */
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        inOrder(root, vals);
        return IntStream.range(1, vals.size()).allMatch(i -> vals.get(i - 1) < vals.get(i));
    }
    
    private void inOrder(TreeNode node, List<Integer> vals) {
        if (node == null) return;
        inOrder(node.left, vals);
        vals.add(node.val);
        inOrder(node.right, vals);
    }
}

解释

方法:

这个题解使用了中序遍历的思路来判断二叉树是否为有效的二叉搜索树。在二叉搜索树中，如果按照中序遍历的顺序遍历节点，得到的序列应该是严格单调递增的。题解定义了一个 lastValue 变量来记录上一个遍历到的节点的值，在递归遍历的过程中，比较当前节点的值和 lastValue，如果当前节点的值小于等于 lastValue，则说明不满足二叉搜索树的性质，返回 False。如果遍历完整个二叉树，没有返回 False，则说明该二叉树是有效的二叉搜索树。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在递归函数中对于`helper(root)`的返回值的处理方式（即是否需要返回特定的值）是如何设计的？为什么有些地方检查了返回值是否为False，而有些地方没有？
▷
在这个题解中，`helper(root)`递归函数用来遍历树并检查是否满足二叉搜索树的条件。这个函数只在发现不合法的情况（即当前节点的值不大于上一个节点的值）时返回`False`。当递归调用`helper(root.left)`或`helper(root.right)`时，如果返回`False`，则意味着已经发现了不满足条件的节点，因此无需继续遍历并直接返回`False`。如果递归调用没有返回`False`，则继续执行下一步的递归调用或操作。这种设计模式是为了提前终止遍历，并快速返回结果，避免不必要的计算。
🦆
如何处理二叉树中包含相同值的节点？题解中提到如果当前节点的值小于等于上一个节点的值则返回False，那么对于具有相同值的节点该如何判定？
▷
根据二叉搜索树的定义，树中的每个节点的值都必须严格大于其左子树中的任何值，并严格小于其右子树中的任何值。因此，如果二叉树中存在具有相同值的节点，则不符合二叉搜索树的定义。在这个题解中，如果发现当前节点的值小于等于上一个遍历到的节点的值，将返回`False`，这包括了节点值相同的情况。因此，具有相同值的节点在此题解中被视为不满足二叉搜索树的条件。
🦆
为什么在开始的检查中，当`root`为`None`时返回`False`？是否有其他较好的处理方式，例如将单个节点的二叉树视为有效的二叉搜索树？
▷
在这个题解中，当`root`为`None`即树为空时返回`False`，这是因为没有节点来进行验证。然而，从定义上讲，一个空的二叉搜索树也是有效的。更好的处理方式是返回`True`当树为空时，因为空树符合二叉搜索树的所有条件。对于单节点的二叉树，它也应当被视为有效的二叉搜索树，因为它自然满足所有左子节点小于根节点，右子节点大于根节点的条件（尽管左右子节点都为空）。
🦆
题解中使用的`lastValue`初始化为负无穷大，这种设计在处理整数以外的数值类型（如浮点数）时是否还适用？
▷
题解中`lastValue`初始化为负无穷大是为了确保第一个节点的值总是大于`lastValue`。这种方法适用于任何数值类型，包括整数和浮点数，因为在Python中，`float('-inf')`是一个特殊的浮点数值，它比所有的浮点数和整数都小。因此，这种初始化方法是通用的，能够确保算法的正确初始条件。

相关问题

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

 

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

 

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

 

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

 

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

 

提示：

  • 树中节点的数目在范围 [1, 104] 内
  • -105 <= Node.val <= 105

 

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

交错字符串恢复二叉搜索树