输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树。

方法一：
需要遍历完整颗树
先设置初始flag为true；
求二叉树的深度；
在求深度过程中，一旦遇到左子树与右子树深度差大于1的情况，设置flag为false；
最后返回flag.

/*
方法一：需要遍历完整棵树
*/
public class Solution {
    boolean flag = true; //先设置flag为true
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }
        getDepth(root); //getDepth()函数是求树的深度的，里面一旦遇到左右子树深度差大于1的情况，就把flag改为false
        return flag;
    }
    public int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if(Math.abs(left-right) > 1){  //左右子树高度差大于一
            flag = false;  //将flag设为false
        }
        return Math.max(left, right)+1;
    }
}

方法二
遇到左子树与右子树的高度差大于1的情况即返回，无需遍历完整棵树。
仍需借助求深度的函数，只是需要改一下这个函数；
getDepth()中，当左子树与右子树高度差大于1时，返回-1，否则返回高度；

/*
方法二：无需遍历完整棵树
*/
import java.lang.Math;

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }
    public int getDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = getDepth(root.left);
        if(left == -1){
            return -1;
        }
        int right = getDepth(root.right);
        if(right == -1){
            return -1;
        }
        //出现左右子树高度差大于一的情况便立即返回-1，否则返回高度
        return Math.abs(left-right)>1?-1:Math.max(left, right)+1;
    }
}