平衡二叉树 （空树或者左右两个孩子高度差不超过1）
在涉及到二叉树的题目时，递归函数非常好用
列出可能性-》整理出返回值的类型-》整个递归过程按照同样的结构得到子树的信息，整合子树的信息，加工出应该返回的信息，向上返回
1.左子树是否平衡
2.右子树是否平衡
3.左子树的高度
4.右子树的高度
根据可能性，使用递归函数
可能性-》返回值的类型
//列出可能性 左右子树是否分别平衡，若平衡后，左右子树的高度
public static class ReturnData{
boolean isB;
int high;
public ReturnData(boolean isB, int high){
this.isB = isB;
this.high = high;
}
}
整个递归过程按照同样的结构得到子树的信息（左子树和右子树分别是否平衡，以及它们的高度），整合子树的信息（左右子树的高度差是否符合要求），加工出返回的信息（应该返回左右子树中，高度较大的那一个high+1）
public static ReturnData process(Tree tree){
if(tree == null) return new ReturnData(true, 0);
ReturnData leftData = process(tree.left);
if(!leftData.isB){
return new ReturnData(false, 0);
}
ReturnData rightData = process(tree.right);
if(!rightData.isB){
return new ReturnData(false, 0);
}
if(Math.abs(leftData.high - rightData.high) > 1){
return new ReturnData(false, 0);
}
return new ReturnData(true, Math.max(leftData.high, rightData.high) + 1);
}
整体的代码
public class IsBanlancedTree {
//列出可能性 左右子树是否分别平衡，若平衡后，左右子树的高度
public static class ReturnData{
boolean isB;
int high;
public ReturnData(boolean isB, int high){
this.isB = isB;
this.high = high;
}
}
public static ReturnData process(Tree tree){
if(tree == null) return new ReturnData(true, 0);
ReturnData leftData = process(tree.left);
if(!leftData.isB){
return new ReturnData(false, 0);
}
ReturnData rightData = process(tree.right);
if(!rightData.isB){
return new ReturnData(false, 0);
}
if(Math.abs(leftData.high - rightData.high) > 1){
return new ReturnData(false, 0);
}
return new ReturnData(true, Math.max(leftData.high, rightData.high) + 1);
}
public static boolean isBanlancedTree(Tree tree){
return process(tree).isB;
}
}
原文：https://www.cnblogs.com/SkyeAngel/p/8947290.html