题目
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
解法：递归套路
平衡树成立条件：
- 左树为平衡二叉树
- 右树为平衡二叉树
- 左树和右树的高度差小于1
需要信息：
- 左树：是否是平衡二叉树、高度
- 右树：是否是平衡二叉树、高度
class Solution {
//返回值类型
public class ReturnType{
public boolean isBalanced;
public int height;
public ReturnType(boolean isB, int hei){
isBalanced = isB;
height = hei;
}
}
public boolean isBalanced(TreeNode root) {
return process(root).isBalanced;
}
//判断是否是平衡二叉树
public ReturnType process(TreeNode root){
//递归出口
if(root == null){
return new ReturnType(true, 0);
}
ReturnType l = process(root.left); //左树返回的信息
ReturnType r = process(root.right); //右树返回的信息
int height = Math.max(l.height,r.height)+1; //下一层的高度+本层的高度
boolean isBalanced = (l.isBalanced && r.isBalanced && Math.abs(l.height - r.height)<2 ); //平衡树成立的三个条件
return new ReturnType(isBalanced, height); //root返回的信息
}
}