题目地址(98. 验证二叉搜索树)

https://leetcode-cn.com/problems/validate-binary-search-tree/

题目描述

  1. 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
  3. 有效 二叉搜索树定义如下：
  5. 节点的左子树只包含 小于 当前节点的数。
  6. 节点的右子树只包含 大于 当前节点的数。
  7. 所有左子树和右子树自身必须也是二叉搜索树。
  11. 示例 1：
  13. 输入：root = [2,1,3]
  14. 输出：true
  17. 示例 2：
  19. 输入：root = [5,1,4,null,null,3,6]
  20. 输出：false
  21. 解释：根节点的值是 5 ，但是右子节点的值是 4 。
  26. 提示：
  28. 树中节点数目范围在[1, 104] 内
  29. -231 <= Node.val <= 231 - 1

前置知识


公司

  • 暂无

思路

image.png
有两个地方有陷阱

  1. 不能单独判断左右子节点是否符合二叉搜索树的定义就完了 还会出现如下情况

image.png
我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点

  1. 样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。 此时可以初始化比较元素为longlong的最小值。

中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 BST，继续遍历；否则直接返回 false。

关键点

  • 中序遍历下，输出的二叉搜索树节点的数值是有序序列。 有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了

代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         //先定义一个最小值 题目中最小值的实例为long.min
  3.         Long pre = Long.MIN_VALUE;
  4.         public boolean isValidBST(TreeNode root) {
  5.             //中止条件 如果遍历到最后没返回false就说明这是一颗二叉搜索树
  6.             if (root == null) {
  7.                 return true;
  8.             }
  9.             //递归调用左边的子树 如果子树返回false 这里也返回false
  10.             if (!isValidBST(root.left)) {
  11.                 return false;
  12.             }
  13.             //pre代表的是前一个数 二叉搜索树的中序遍历顺序就是从大到小的顺序
  14.             // 所以这里只需要判断前一个数是否小于当前节点值即可 如果不小于就返回false
  15.             if (pre >= root.val) {
  16.                 return false;
  17.             }
  18.             //如果到这里就说明前一个数字小于当前数 使当前数变为下一个数的最小值
  19.             pre = Long.valueOf(root.val);
  20.             return isValidBST(root.right);
  21.         }
  22.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：98. 验证二叉搜索树 - 图3#card=math&code=O%28n%29&id=gI17M)
  • 空间复杂度：98. 验证二叉搜索树 - 图4#card=math&code=O%28n%29&id=pVwkM)