BM34. [判断是不是二叉搜索树]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM34. 判断是不是二叉搜索树
题目分析
还记得二叉搜索树与双向链表这个里面使用的中序遍历吗？既然是判断是否是二叉搜索树那我们可以继续使用中序遍历。只要之前的节点是二叉树搜索树，那么如果当前的节点小于上一个节点值那么就可以向下判断。*只不过在过程中我们要求反退出
具体做法
方法一
比如一个链表
1->2->3->4 只要 for循环遍历如果中间有不是递增的直接返回false即可。
具体做法首先递归到最左，初始化maxLeft与pre，然后往后遍历整棵树，依次连接pre与当前结点，并更新pre
- 左子树如果不是二叉搜索树返回false
- 判断当前节点是不是小于前置节点，更新前置节点
- 最后由右子树的后面节点决定
代码其实就是，其实这个就是类似判断链表递增的一个中序遍历
int pre = Integer.MIN_VALUE;
//判断是不是搜索二叉树
public boolean isValidBST (TreeNode root) { //中序遍历
if (root == null)
return true;
//更新最值
if(!isValidBST(root.left))
return false;
if (root.val < pre)
return false;
//向后遍历
pre = root.val;
return isValidBST(root.right);
}
方法二
当然我们代码也可不取反退出而是将每种二叉树的方式全部都输出出来即可，这样需要考虑的情况稍微多一点。但是可以不去创建pre那个前驱节点
public boolean isSearch(TreeNode root){
if(root == null)
return true;
// 左右子节点都不空
if(root.left != null && root.left.val <= root.val
&& root.right != null && root.right.val >= root.val){
return isSearch(root.left) & isSearch(root.right);
}
// 左节点空 右节点不空
if(root.left == null && root.right != null && root.right.val >= root.val ){
return isSearch(root.right);
}
// 左节点不空 又节点空
if(root.right == null && root.left != null && root.left.val <= root.val){
return isSearch(root.left);
}
//左右节点都空
if(root.left == null && root.right == null){
return true;
}
return false;
}
