算法题(三十二):判断二叉树是否是*衡二叉树

发布于:2021-09-22 03:46:44

7.?判断是否是BST


题目描述

输入一棵二叉树,判断该二叉树是否是*衡二叉树。


分析

可以用递归的方法,从下向上遍历各个结点(后序遍历),如果结点是满足BST的条件则返回该结点的高度,如果不满足则直接停止遍历并返回false。



代码

public class IsBlanceTree {

public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode root = new TreeNode(1);
root.left = new TreeNode(1);
root.left.left = new TreeNode(1);
root.right = new TreeNode(1);
root.right.left = new TreeNode(1);
root.right.right = new TreeNode(1);
if(getDepth(root) != -1){
System.out.println(true);
}else{
System.out.println(false);
}
}

public static int getDepth(TreeNode root){
if(root == null){
return 0;
}
int left = getDepth(root.left);
if(left == -1){
return -1;
}
int right = getDepth(root.right);
if(right == -1){
return -1;
}
return Math.abs(left-right)>1?-1:1+Math.max(left, right);
}

}

相关推荐

最新更新

猜你喜欢