If you know the last commit message of the deleted branch you can do this:
git reflog
# search for message
fd0e4da HEAD@{14}: commit: This is the commit message I want
# checkout revision
git checkout fd0e4da
or
git checkout HEAD@{14}
# create branch
git branch my-recovered-branch
# push branch
git push origin my-recovered-branch:my-recovered-branch