110. Balanced Binary Tree

第一种递归：在isBalanced中，对于一个root节点，用getDepth递归求出它左右两边的高度，再在isBalanced函数中进行递归。

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int ll = getDepth(root.left);
    int lr = getDepth(root.right);
    return Math.abs(ll - lr) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

public int getDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
}

第二种：把所有逻辑写在getDepth中，也就是在求高度的同时进行判断层数是否大于1，只需要对节点进行一次遍历。

public boolean isBalanced(TreeNode root) {
    if (getDepth(root) == -1) {
        return false;
    }
    return true;
}

public int getDepth(TreeNode root) {
    if (root == null) return 0;
    int ll = getDepth(root.left);
    int lr = getDepth(root.right);
    if (Math.abs(ll - lr) > 1 || ll == -1 || lr == -1) return -1;
    return Math.max(ll, lr) + 1;
}

这里这个条件是用来判断如果返回的root中左右两个节点的高度若有一个为-1，也就是它不是平衡二叉树，那么root也返回-1，整个树都不是平衡二叉树。

if (Math.abs(ll - lr) > 1 || ll == -1 || lr == -1) return -1;