What is your OS?
If the folder was on the local drive, it is moved to trash and not deleted.
If the folder is on a network drive, it is gone for good.
Simply copy the files back in from your backup and relink in LR (do not delete in LR, the folder missing should now be shown with '?').
Did you use your operating system to search for the photos by file name?
If you did, and searching by operating system function fails to find the photos, then you probably have been bitten by a rare but serious bug in Lightroom, which is described in reply 1 in this thread
For future use, you should move photos using your operating system (not Lightroom) and then reconnect in Lightroom using these instructions: Adobe Lightroom - Find moved or missing files and folders
Hi - my OS is Mac OS 10.10.4, and it was on an external drive. Sounds like they are gone for good. They were a recent import and didn't get backed up.
Ah, rats. Lesson learned. I'll move things via OS and reconnect as you suggest. Thank you to all who responded.