Intuition on O(number of leaves) for master theorem
The recurrence in question is $T(n) = aT(n/b) + f(n)$. Suppose that $n = b^k$, and the leaves are at $n = 1$. The root $b^k$ has $a$ children labelled $b^{k-1}$ (the label is the size of the subproblem). Each one of them has $a$ children labelled $b^{k-2}$, and in total there are $a^2$ children at depth $2$ labelled $b^{k-2}$. More generally, there are $a^\ell$ children at depth $\ell$ labelled $b^{k-\ell}$. In particular, taking $k = \ell$, we see that there are $a^k$ leaves. Since $n = b^k$, we get that the number of leaves is
$$
a^k = (b^{\log_b a})^k = (b^k)^{\log_b a} = n^{\log_b a}.
$$