GNU find has a -delete action. It implies -depth and as such, can do the clean-up in one go.