  We initiate a detailed and systematic study of automorphisms of the Cuntz
algebras $\O_n$ which preserve both the diagonal and the core $UHF$-subalgebra.
A general criterion of invertibility of endomorphisms yielding such
automorphisms is given. Combinatorial investigations of endomorphisms related
to permutation matrices are presented. Key objects entering this analysis are
labeled rooted trees equipped with additional data. Our analysis provides
insight into the structure of ${\rm Aut}(\O_n)$ and leads to numerous new
examples. In particular, we completely classify all such automorphisms of
${\mathcal O}_2$ for the permutation unitaries in $\otimes^4 M_2$. We show that
the subgroup of ${\rm Out}(\O_2)$ generated by these automorphisms contains a
copy of the infinite dihedral group ${\mathbb Z} \rtimes {\mathbb Z}_2$.
