Before starting, you need your git client configured.

            var credentials = new VssBasicCredential(userName: string.Empty, password: this.config.Key);
            this.vssConnection = new VssConnection(new Uri(this.config.BaseUrl), credentials);
            if (!string.IsNullOrWhiteSpace(this.config.Key))
            {
                this.gitClient = this.vssConnection.GetClient<GitHttpClient>(); // Creates a git client.
            }

Install Azure DevOps SDK from nuget:

(In your csproj)

		<!--Azure DevOps-->
		<PackageReference Include="Microsoft.TeamFoundationServer.Client" Version="16.170.0" />

Code:

        /// <summary>
        /// Restore a deleted branch.
        /// </summary>
        /// <param name="branch">Branch name</param>
        /// <returns>Restore task</returns>
        public async Task<bool> RestoreBranch(string branch)
        {
            var searchCriteria = new GitPushSearchCriteria
            {
                RefName = $"refs/heads/{branch}",
                IncludeRefUpdates = true
            };

            var pushes = await this.gitClient.GetPushesAsync(
                project: this.config.ProjectName,
                repositoryId: this.config.RepositoryId,
                skip: 0,
                top: 1,
                searchCriteria: searchCriteria);

            if (!pushes.Any() || !pushes.First().RefUpdates.Any())
            {
                return false;
            }

            var refUpdate = pushes.First().RefUpdates.First();
            var objectId = refUpdate.OldObjectId;
            var updates = new List<GitRefUpdate>
            {
                new GitRefUpdate
                {
                    Name = $"refs/heads/{branch}",
                    NewObjectId = objectId,
                    OldObjectId = "0000000000000000000000000000000000000000" // Deleted object.
                }
            };

            var result = await this.gitClient.UpdateRefsAsync(
                refUpdates: updates, 
                repositoryId: this.config.RepositoryId, 
                project: this.config.ProjectName);

            return result.Any() && result.First().Success;
        }

After running that, you can run git fetch locally. Now the delete branch gonna appear.