判断平衡二叉树
【摘要】 平衡二叉树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。并且左右两个子树都是一棵平衡二叉树
(不是我们平时意义上的必须为搜索树)
判断一棵树是否为平衡二叉树:
可以暴力判断:每一颗树是否为平衡二叉树。
分析:
如果左右子树都已知是平衡二叉树,而左子树和右子树高度差绝对...
平衡二叉树(Balanced Binary Tree)具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。并且左右两个子树都是一棵平衡二叉树
(不是我们平时意义上的必须为搜索树)
判断一棵树是否为平衡二叉树:
可以暴力判断:每一颗树是否为平衡二叉树。
分析:
如果左右子树都已知是平衡二叉树,而左子树和右子树高度差绝对值不超过1,本树就是平衡的。
为此我们需要的信息:左右子树是否为平衡二叉树。左右子树的高度。
我们需要给父返回的信息就是:本棵树是否是平衡的、本棵树的高度。
定义结点和返回值:
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static class ReturnType {
public int level; //深度
public boolean isB;//本树是否平衡
public ReturnType(int l, boolean is) {
level = l;
isB = is;
}
}
我们把代码写出来:
// process(head, 1)
public static ReturnType process(Node head, int level) {
if (head == null) {
return new ReturnType(level, true);
}
//取信息
ReturnType leftSubTreeInfo = process(head.left, level + 1);
if(!leftSubTreeInfo.isB) {
return new ReturnType(level, false); //左子树不是->返回
}
ReturnType rightSubTreeInfo = process(head.right, level + 1);
if(!rightSubTreeInfo.isB) {
return new ReturnType(level, false); //右子树不是->返回
}
if (Math.abs(rightSubTreeInfo.level - leftSubTreeInfo.level) > 1) {
return new ReturnType(level, false); //左右高度差大于1->返回
}
return new ReturnType(Math.max(leftSubTreeInfo.level, rightSubTreeInfo.level), true);
//返回高度和true(当前树是平衡的)
}
我们不需要每次都返回高度,用一个全局变量记录即可。
对于其它二叉树问题,可能不止一个变量信息,所以,全局记录最好都养成定义数组的习惯。
下面贴出完整代码:
import java.util.LinkedList;
import java.util.Queue;
public class Demo {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isBalance(Node head) {
boolean[] res = new boolean[1];
res[0] = true;
getHeight(head, 1, res);
return res[0];
}
public static class ReturnType {
public int level; //深度
public boolean isB;//本树是否平衡
public ReturnType(int l, boolean is) {
level = l;
isB = is;
}
}
// process(head, 1)
public static ReturnType process(Node head, int level) {
if (head == null) {
return new ReturnType(level, true);
}
//取信息
ReturnType leftSubTreeInfo = process(head.left, level + 1);
if(!leftSubTreeInfo.isB) {
return new ReturnType(level, false); //左子树不是->返回
}
ReturnType rightSubTreeInfo = process(head.right, level + 1);
if(!rightSubTreeInfo.isB) {
return new ReturnType(level, false); //右子树不是->返回
}
if (Math.abs(rightSubTreeInfo.level - leftSubTreeInfo.level) > 1) {
return new ReturnType(level, false); //左右高度差大于1->返回
}
return new ReturnType(Math.max(leftSubTreeInfo.level, rightSubTreeInfo.level), true);
//返回高度和true(当前树是平衡的
}
public static int getHeight(Node head, int level, boolean[] res) {
if (head == null) {
return level;//返回高度
}
//取信息
//相同逻辑
int lH = getHeight(head.left, level + 1, res);
if (!res[0]) {
return level;
}
int rH = getHeight(head.right, level + 1, res);
if (!res[0]) {
return level;
}
if (Math.abs(lH - rH) > 1) {
res[0] = false;
}
return Math.max(lH, rH);//返回高度
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
System.out.println(isBalance(head));
}
}
文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。
原文链接:fantianzuo.blog.csdn.net/article/details/84260028
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)