JZ39-平衡二叉树

自底向上
其实可以直接在求高度的同时，直接判断即可。
利用后序遍历：左子树、右子树、根节点,可以先递归到叶子节点，然后在回溯的过程中来判断是否满足条件。
时间复杂度:O(n)
空间复杂度:O(n)

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root) != -1;
    }
    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = depth(root.left);
        if (left == -1) {
            return -1;
        }
        int right = depth(root.right);
        if (right == -1) {
            return -1;
        }
        if (left - right < (-1) || left - right > 1) {
            return -1;
        } else {
            return 1 + (left > right ? left : right);
        }
    }
}