98.验证二叉搜索树
- 验证二叉搜索树
难度中等513
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入: 2 / 1 3 输出: true
示例 2:
输入: 5 / 1 4 / 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。
1.中序遍历
//inoder 遍历的结果就是一个有序的对于BST来说,
//因此 我们借助stack 左一次inorder 记录每一次的当前值和下一个值比较
//如果下一个值小于上一个值 说明 不是BST。否则就是
//因此 先迭代左子节点 在迭代右子节点
//time : O(n) 每一个节点有且仅被访问一次
//space : O(n) 借助一个stack结构存储节点。
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
double minValue = -Double.MAX_VALUE;
while(!stack.isEmpty() || root != null){
while(root!=null){
stack.push(root);
root = root.left;//递归左子节点
}
root = stack.pop();
if(root.val <= minValue) return false; //如果小于最小值 非BST
minValue = root.val;
root = root.right;//递归右子节点
}
return true;
}
2.递归
time:o(n)
//递归
//主要思路 就是通过递归查找根节点的左子树的最大值是否大于根节点
//或者根节点的右子树的最小值是否小于根节点。
public boolean isValidBST(TreeNode root) {
return isValid(root,null,null);
}
public boolean isValid(TreeNode root,Integer min,Integer max){
//如果根节点为null 返回true
if(root == null) return true;
if(min != null && root.val <= min) return false;
if(max != null && root.val >= max) return false;
return isValid(root.left,min,root.val) && isValid(root.right,root.val,max);
}