Contrary to popular belief, deleted projects are not actually deleted. Only the reference to the reports are deleted, but you can recover projects if you need to....
The key is using the Admin Logs to find the project Id.
The Event field is a contains logic, so you just have to add "Project Deleted" and choose a date range (note, you can only look at 3 months at a time, hopefully you know when the project was deleted)
This will return all the records of the deletions, with the Project ID.
Copy that ID.
Now, open any other project, and replace the Project ID in the URL with the ID from the "deleted" report.
This will open the supposedly deleted report, and you can re-save or save as.
That said, I think having a recycling bin would make this process a lot easier, so I am still going to upvote. But I assume this is coming from a place of "oh shoot, I or someone else deleted a report that I need... now I need to rebuild it..." This can help you in the meantime.