平衡二叉树

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

• 思路
  法一：每次判断当前树的左右子树高度差，然后判断子树的子树。
  法二：由于每次求子树的高度，导致很多节点被重复计算，因此在计算的过程中就应该判断是否符合平衡二叉树的性质。当高度返回-1时代表不是平衡二叉树，这样就实现了从下往上判断，且每个节点被计算一次。时间复杂度为O(n)

//法一
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null)
            return true;
        
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(Math.abs(leftHeight - rightHeight) > 1)
            return false;
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    
    public int getHeight(TreeNode root){
        if(root == null)
            return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

//法二
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null)
            return true;
        
        if(getHeight(root) == -1)
            return false;
        return true;
    }
    
    public int getHeight(TreeNode root){
        if(root == null)
            return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(Math.abs(leftHeight - rightHeight) > 1)
            return -1;
        if(leftHeight == -1 || rightHeight == -1)
            return -1;
        return Math.max(leftHeight, rightHeight) + 1;
    }
}