I did the same. Deleted someone else's branch from a Gitlab repo that I did not have locally, so "git reflog" was no help. I then found another answer regarding recovering a Github deleted branch, Git: Recover deleted (remote) branch which suggested if you used JIRA or something like it that would have a link to the commit and sure enough the link was there and clicking on it brought me right to the commit. The link contains the SHA1 id of the commit to use in @diego-baranowski answer.
git checkout -b <branchname> <sha1>
where "branchname" can be any name you want, the same as the deleted branch name or a new name and "sha1" is the long SHA1 id of the commit.
Alternatively, you can use curl (or better yet) Postman to list the events on the GitLab server and find the "deleted" event that you did which will also have the SHA1 id in it (the "commit from" value).
curl --location --request GET 'https://gitlab.com/api/v4/events' --header 'Authorization: Bearer <your Personal Access Token here>
Returns JSON like this:
{
"id": xxxx,
"project_id": xxxx,
"action_name": "deleted",
"target_id": null,
"target_iid": null,
"target_type": null,
"author_id": xxxx,
"target_title": null,
"created_at": "2021-11-08T20:27:56.299Z",
"author": xxxx,
"push_data": {
"commit_count": 0,
"action": "removed",
"ref_type": "branch",
"commit_from": "<YOUR SHA1 ID IS HERE>",
"commit_to": null,
"ref": "<DELETED NAME HERE>",
"commit_title": null,
"ref_count": null
},
"author_username": "xxxx"
},