public class BalancedBinaryTreeSolution {
    /**
     * 访问局部内部类必须先有外部类对象,此处必须用Static修饰
     */
//    public static class TreeNode {
//           int val;
//           TreeNode left;
//           TreeNode right;
//           TreeNode(int x){ val = x;}
//    }
    
    //OJ支持JDK的Math函数
    public boolean isBalanced(TreeNode root) {
        //注意空树的情况
        if(root == null)
            return true;
        
        int leftDepth=getDepth(root.left);
        int rightDepth=getDepth(root.right);
        int altitude=rightDepth-leftDepth;
        //注意只有一个顶点的情况
        if(Math.abs(altitude)>1)
            return false;            
        else
            //递归比较
            return isBalanced(root.left) && isBalanced(root.right);
    }
    
    private int getDepth(TreeNode node){
        if(node == null)
            return 0;
        //递归求深度
        return  1+Math.max(getDepth(node.left), getDepth(node.right));
    }
}