题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

代码一

思想:自下往上的遍历每一个节点,求出每一个节点的深度,只要有一个不符合平衡二叉树的要求就返回-1退出函数;

  1. public static int depth(TreeNode root) {
  2.         if(root==null)return 0;
  3.         int left = depth(root.left);
  4.         if(left==-1)return -1;
  5.         int right = depth(root.right);
  6.         if(right==-1)return -1;
  7.         return Math.abs(left-right)>1? -1:1+Math.max(left,right);        
  8.     }
  9.     public boolean IsBalanced_Solution(TreeNode root) {
  10.         return depth(root) != -1;
  11.     }

代码二

思想:
自顶往下
平衡二叉树的定义是左右子树高度差不超过1，同时左右子树也是平衡二叉树，于是代码逻辑可以如下
1.判断树是否为空，空则返回true
2.判断左右子树深度差，其中，求树深度的函数在上一题中“二叉树的深度中”已实现，差超过1，返回false
3.若通过2的判断，对左右子树也判断是否都是平衡二叉树，判断函数为函数自身，递归调用

  1. public class Solution {
  2.     public int TreeDepth(TreeNode root) {
  3.         if(root==null){
  4.             return 0;
  5.         }
  6.         if(root.left==null && root.right==null){
  7.             return 1;
  8.         }
  9.         return 1+Math.max(TreeDepth(root.left),TreeDepth(root.right));
  10.     }
  11.     public boolean IsBalanced_Solution(TreeNode root) {
  12.         if(root==null) return true;
  13.         if(Math.abs(TreeDepth(root.left)-TreeDepth(root.right))>1)
  14.             return false;
  15.         return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);//不断的自顶向下递归
  16.         //找出每个节点的深度然后通过第二个if来判断,这样的话会多次重复遍历下层结点，增加了不必要的开销
  17.     }
  18. }