题目
验证二叉搜索树
给你一个二叉树的根节点 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
题解
解题分析
解题思路
- 结合题意可以知道：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
- 我们可以设计一个递归方法
isValidBST(TreeNode node, long lower, long upper)来判断 node 参数考虑以 root 根节点为参数，判断树的所有节点值值是否都在（lower，upper）范围内。如果 root 节点的值 val 不在(lower, upper )返回内说明不满足条件直接返回，否者继续检索，直到检索完毕才说明是一个二叉搜索数。
- 在递归调用的过程中，我们
（lower, upper）首次可以使用 int 的最大值，最小值。 在每次调用的过程中，左子树的 upper 值为 当前值 node.val , 右子树的 lower 值为 当前值 node.val 。
- 递归方法的出口由两种情况，第一种是 node == null 返回 true , 第二种就是 node.val 是否在 lower 和 upper 区间内，如果不在返回 false.
复杂度
时间复杂度 O(N)
空间复杂度 O(N)
解题代码
题解代码如下（代码中有详细的注释说明）：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root , Long.MIN_VALUE, Long.MAX_VALUE); } // 递归校验方法 public boolean isValidBST(TreeNode node, long lower, long upper) { // 如果为 null 表示合法 if (node == null) { return true; } // 注意这里是开区间范围内合法 if (node.val <= lower || node.val >= upper) { return false; } // left , right 分别判断，和设置 lower, upper 的值 return isValidBST(node.left, lower, node.val ) && isValidBST(node.right, node.val, upper); } }
提交后反馈结果如下：
网络异常，图片无法展示
|
