题目
给你一个二叉树的根节点
root
,判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
-2^31 <= Node.val <= 2^31 - 1
解题思路
- 需要当前节点的值和父节点作比较,所以基础方法无法满足需要对方法进行重载或建立新的函数;
- val的值超出Integer.MAX_VALUE所以需要通过Long的最大最小值来进行初始化赋值;
- 循环结束条件,当前节点为空;
- 限定当前节点val的取值范围,并进行递归循环。
代码展示
class Solution { public boolean isValidBST(TreeNode root) { return isVaild(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean isVaild(TreeNode root, long min, long max){ if (root == null) { return true; } long x = root.val; return min < x && x < max && isVaild(root.left, min, x) && isVaild(root.right, x, max); } }