剑指Offer第三十九题：平衡二叉树

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

思路：
平衡二叉树要求左子树和右子树的高度差不超过一，同时左右子树也是平衡二叉树；
深度优先遍历，先从叶节点开始判断，如果是平衡二叉树那么返回树的高度，如果不是则返回-1；
下面的写法修剪了多余的部分，如果左子树不是平衡二叉树，那么右子树就没有必要判断了，直接返回-1；

public boolean IsBalanced_Solution(TreeNode root) {

    return getDepth(root) != -1;
}

private 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;
    return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
}

}