方法一(递归实现)
1、特点
- 搜索树——左结点的value都是小于头结点的,右结点的value都是大于头结点的。
- 搜索树——中序遍历是升序排序的。
2、方法主体
- 中序遍历时——中间是打印,如今可以换成判定条件
- 判定条件——因为中序遍历时是升序的,所以,当前节点的value值是大于上一个节点的value值的——所以只用判断这两个节点值即可。
- 比较方法——这时我们可以定义一个全局变量保存上一个节点值——因为递归函数没每次都会从头出发——所以应该定义一个在方法外的变量来保存上一个节点值。
- 判断结果——当前节点的value值小于上一个节点值时,返回false,反之返回true。
- 代码如下
//判断树是否是搜索二叉树---二叉什排序树
long preValue = Long.MIN_VALUE; //全局变量统计上一个节点的值
public boolean isBst(TreeNode treeNode){
if (treeNode == null){
return true;
}
boolean flag = isBst(treeNode.left); //递归左子树
if (!flag){ //当左子树递归完后----判断flag的值---观察是否为false
return false;
}
if (treeNode.value <= preValue){ //让当前结点的值与上一个结点的值作对比
return false;
}else{
preValue = treeNode.value; //保存上一个结点的值
}
return isBst(treeNode.right); //递归右子树
}
方法二(递归加集合)
1、特点
- 简单明了
- 采用集合能更好的做判断
2、方法主体
- orderList方法:–>通过集合按顺序收集—二叉树中序遍历的值
- isBst1方法:–> 遍历集合里面的值——并通过当前节点的value值是大于上一个节点的value值这一条件来进行判断——是否为搜索树
- 代码如下
public boolean isBst1(TreeNode root){
List<TreeNode> list = new ArrayList<>();
orderList(root,list);
boolean flag = true;
for (int i = 0;i<list.size()-1;i++){
if (list.get(i+1).value <= list.get(i).value){ //进行节点值判断
flag = false;
}
}
return flag;
}
public void orderList(TreeNode root,List<TreeNode> list){
if (root == null){
return;
}
orderList(root.left,list);
list.add(root); //存入树节点信息
orderList(root.right,list);
}
方法三(非递归方法—栈)
1、方法
- 在栈弹出节点的时候进行判断
判断树是否是搜索二叉树---法三
public boolean isBst2(TreeNode root){
int temp = Integer.MIN_VALUE;
if (root != null) {
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root !=null){
if (root !=null){
stack.push(root);
root = root.left;
}else {
root = stack.pop();
if (root.value <= temp){
return false;
}else{
temp = root.value;
}
root = root.right;
}
}
}
return true;
}
以上代码均通过力扣–>验证搜索二叉树
版权声明:本文为weixin_51713937原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。