需求
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左
子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
注意： 二叉搜索树中序遍历，元素是有序单调递增的。
思路
根据搜索二叉树的概念使用递归中序遍历左中右的形式更方便一些，验证完左子树验证根节点，再验证右子树节点。完成整棵树值的验证。
/**
*
*98. 验证二叉搜索树
*/
public class IsValidBST98 {
Long maxVal = Long.MIN_VALUE;
/**
* 递归方式
* 有些测试用例比int最小值还小
* 如果值小于最小值直接返回false，这个实现方式会有这个问题
*/
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
boolean left = isValidBST(root.left);
if (root.val > maxVal) {
maxVal = (long) root.val;
} else {
return false;
}
boolean right = isValidBST(root.right);
return left && right;
}
private TreeNode preNode = null;
/**
* 递归方式
*/
public boolean isValidBST1(TreeNode root) {
if (root == null) return true;
boolean left = isValidBST(root.left);
if (preNode ==null || root.val > preNode.val) {
preNode = root;
} else {
return false;
}
boolean right = isValidBST(root.right);
return left && right;
}
}
验证结果
