110 Balanced Binary Tree

GUO

    // balance这个问题本身就包含两个recursion, 一个recursion要看左右子树的height
    // 另一个是左右子树高度的比较也是一个大小问题的分治.
    public boolean isBalanced(TreeNode root) {
        if (null == root) {
            return true;
        }
        // 如果小问题是false,大问题的解也会是false,因此可以用一层一层返回
        // 传递false来合并.
        if (!isBalanced(root.left)) {
            return false;
        }
        if (!isBalanced(root.right)) {
            return false;
        }

        int delta = getHeight(root.left) - getHeight(root.right);
        return delta >= -1 && delta <= 1;
    }

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