一、问题:

  请实现一个函数,检查一棵二叉树是否为二叉查找树。给定树的根结点指针TreeNode* root,请返回一个bool,代表该树是否为二叉查找树。

二、思路: 

  解法一:从根节点开始遍历二叉树,其中需要使用到递归进行遍历节点,判断根的左右节点的值与根节点的值的大小的比较,其中递归的思路是假如树有左子树那么我们遍历左子树,有右子树那么遍历右子树,左右子树都有那么我们遍历左右子树,为叶子节点的时候直接返回true即可。除了上面的判断之外还不够,还需要判断左子树中最大的节点值是否小于根节点的值,右子树中最小的节点的值是否大于根节点的值。

  解法二: 首先我们想到的是二叉树中序遍历后的结果是有序的,根据这个结果,我们可以中序遍历二叉树,并把遍历结果存放在一个数组里面,然后判断这个数组大小是否是有序数组,如果是有序数组,则是二叉查找树,否则就不是。  这个方法的时间复杂度是O(N),但是空间复杂度比较高,需要浪费O(N)的存储空间。

import java.util.ArrayList;

public class CheckBST1 {
// 中序遍历是否有序
public boolean checkBST(TreeNode root) {
if (root == null)
return false;
ArrayList<Integer> list = new ArrayList<>();
inorder(root, list);
return checkOrdered(list);
} // 递归方式把节点按中序遍历顺序加入到列表中
private void inorder(TreeNode<Integer> node, ArrayList<Integer> list) {
if (node == null)
return;
if (node.left != null) {
inorder(node.left, list);
}
list.add(node.val);
if (node.right != null) {
inorder(node.right, list);
}
} // 遍历列表,前后两两比较,如果逆序,返回false
private boolean checkOrdered(ArrayList<Integer> list) {
for (int i = 0; i < list.size() - 2; i++) {
if (list.get(i) > list.get(i + 1))
return false;
}
return true;
} public static class TreeNode<T> { public T val;
public TreeNode<T> left = null;
public TreeNode<T> right = null;
public TreeNode<T> parent = null; public TreeNode(T val) {
this.val = val;
} }
}

  解法三:中序遍历,全局变量记录上一个值,当前值必须大于上一个值。满足条件更新pre为当前值。

 public class CheckBST2 {
public boolean checkBST(TreeNode<Integer> root) {
if (root == null)
return true; // 检查左子树,如果左子非bst立即返回false
boolean leftIsBST = checkBST(root.left);
if (!leftIsBST)
return false;
// 根的值小于等于左子树的最大值,返回false
if (root.val <= preValue) {
return false;
}
// 更新最后访问的值,检查右子树
preValue = root.val;
return checkBST(root.right);
} private int preValue = Integer.MIN_VALUE; public static class TreeNode<T> { public T val;
public TreeNode<T> left = null;
public TreeNode<T> right = null;
public TreeNode<T> parent = null; public TreeNode(T val) {
this.val = val;
} }
}

最新文章

  1. POJ1390Blocks(DP+好题+抽空再来理解理解)
  2. jquery easyui 动态绑定数据列
  3. javascript之享元模式
  4. javascript栈的建立样码
  5. grails的layouts模板页面使用
  6. HDU4815
  7. inline-block 前世今生
  8. OpenWrt编译到底脚本
  9. android button 字母自动大写
  10. tomcat源码阅读
  11. VS2013程序打包部署(图解),vs2013部署
  12. postgresql赋予/撤消 用户权限
  13. go语言初体验
  14. 依据二度人脉推荐好友sql
  15. STM32 一通道单次转换
  16. 用Xamarin + VS 编写Android程序体验及其与Android Studio的比较
  17. 新篇章之我的java学习之路上
  18. CentOS 6.5 安装mysql 过程记录
  19. lrzsz linix 远程文件传输工具。
  20. SQL 中的语法顺序与执行顺序

热门文章

  1. python中hasattr()、getattr()、setattr()函数的使用
  2. git增加子模块
  3. Gradle 同步时报错,Could not find com.android.support.constraint:constraint-layout:1.0.0-alpha8的解决方法
  4. Java Swing 编程 JComboBox 实现模糊查找功能。
  5. 设置Jexus开机启动
  6. IntelliJ IDEA 如何设置类头注释和方法注释
  7. Helm - Kubernetes服务编排的利器
  8. SQL Server Agent Job 中用Powershell将备份文件拷贝到AWS S3
  9. python-while else
  10. ORM之SQLALchemy