前言
本文介绍什么是平衡二叉树以及如何判断一个二叉树是否是平衡二叉树。
正文
什么是平衡二叉树呢？在一棵二叉树里，他的任意一个节点的左树的最大高度和右树的最高高度相差的绝对值不超过1。
如下图，图中任意一个节点，它的左树最大高度和右树的最大高度的差都不超过1，所以他是平衡二叉树。
再如下图，就不是平衡二叉树，以节点a来说，节点a的左树最大高度为3，节点a的右树最大高度为1，左右高度相差为2，所以下图这个二叉树不是平衡二叉树。
思路分析
本次依然采用递归的套路来分析如何判断一棵二叉树是否为平衡二叉树。
给出一个节点node，要判断该节点是否为平衡二叉树的话，我们需要以下几点来判断：
节点node的左树必须是平衡二叉树节点node的右树必须是平衡二叉树节点node的左树高度和右树高度的差值不能超过1
在采用递归时，对于任意一个节点，需要知道这个节点的左树是否为平衡二叉树以及左树的高度，同样的，需要知道这个节点的右树是否为平衡二叉树以及右树的高度。
所以，我们根据分析得出，需要创建一个类，这个类有两个属性：是否是平衡二叉树、数的高度。
创建递归函数，这个函数接收一个节点参数，然后分别判断这个节点的左树和右树即可。
代码实现
定义二叉树的节点，代码如下：
public class Node {
public int value;
public Node left;
public Node right;
}
定义一个信息类，用来接收递归返回的是否是平衡二叉树、数的高度，代码如下：
public class Info{
public boolean isBalanced;
public int height;
public Info(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
递归判断二叉树逻辑如下：
public Info process(Node node) {
// 基础信息，baseline
if(node == null) {
return new Info(true, 0);
}
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
// 节点的高度
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
boolean isBalanced = true;
// 左树是否平衡
if(!leftInfo.isBalanced) {
isBalanced = false;
}
// 右树是否平衡
if(!rightInfo.isBalanced) {
isBalanced = false;
}
// 左右两遍的高度差
if(Math.abs(leftInfo.height - rightInfo.height) > 1) {
isBalanced = false;
}
return new Info(isBalanced, height);
}
在递归过程中，先默认这个节点是平衡二叉树isBalanced=true，再看下有哪些地方违反了平衡二叉数的定义，如果违反了则改为false即可，代码中如果左树不是平衡的，则该节点也不是平衡的；如果右树不是平衡点，则该节点不是平衡的；如果左右高度差大于1，则也不是平衡的，否则的话，这个节点就是平衡的。
剩下的就是主函数调用了，在调用的时候，只需要拿到Info的isBalanced即可，因为最终返回的是是否为平衡二叉树。
public boolean isBalanced(Node head) {
return process(head).isBalanced;
}
总结
本文介绍什么是平衡二叉树以及如何判断一个二叉树是否是平衡二叉树，在本次分析过程中，虽然只需要一个是否为平衡二叉树的结果，但在实现过程中，我们定义了一个Info类，这个是为了让递归过程更方便。
其实这也是递归过程中的一个套路，让递归过程统一化，让左右两边收集的信息格式一致，利用好这个套路的话，再遇到类似的题目，只需要把框架往上一套就可以了。
若有收获就点个赞吧^_^
