##题目描述
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
##思路
如果每个节点的左右子树的深度相差都不超过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,则为平衡二叉树 } }