##题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
##思路
如果每个节点的左右子树的深度相差都不超过1，即最大深度差为1，则可判定为平衡二叉树。
两种思路：
第一种是递归判断每一个根节点，都要求出它的左右子树的深度，深度相差小于1即可（根左右），可以理解为自顶向下。
第二种是从自己的左右子树开始判断用一个数组来记录深度（为防止归零，所以用引用类型）只要自己的左右深度条件都满足，则该树满足，不需要重复计算深度。（左右根），可以理解为自底向上
##代码
第一种思路
/** * */ package offerTest; /** * <p> * Title:Balance * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月21日 上午9:45:44 */ public class Balance { public boolean IsBalanced(TreeNode root) { if (root == null) { // 递归结束条件 return true; } int diff = Math.abs(deep(root.left) - deep(root.right)); // 求绝对值函数 if (diff > 1) { return false; // 如果相差大于1，返回false } return IsBalanced(root.left) && IsBalanced(root.right); // 递归检查每一个几点 } // 求节点深度函数 public int deep(TreeNode root) { if (root == null) { return 0; } return deep(root.left) > deep(root.right) ? deep(root.left) + 1 : deep(root.right) + 1; } }
第二种思路：优化算法
/** * */ package offerTest; import 二叉树.TreeNode; /** * <p> * Title:Balance * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月21日 上午9:45:44 */ public class Balance { // 优化算法 public boolean IsBalancedSuper(TreeNode root) { int[] depth = new int[1]; return isBalance(root, depth); } public boolean isBalance(TreeNode root, int[] depth) { if (root == null) { depth[0] = 0; return true; } boolean leftbalance = isBalance(root.left, depth); int leftdepth = depth[0]; boolean rightbalance = isBalance(root.right, depth); int rightdepth = depth[0]; depth[0] = Math.max(leftdepth + 1, rightdepth + 1); // 取二者最大为深度 return leftbalance && rightbalance && Math.abs(rightdepth - leftdepth) < 1; // 如果左右子树都平衡，且相差小于1，则为平衡二叉树 } }
