You can try using a partition recovery tool to try rebuilding the partition tables and hopefully restoring the filesystem on the drive so it provides the system with a properly set up Time Machine drive; however, this will be a hit or miss success.
One tool that may work here is TestDisk: http://www.cgsecurity.org/wiki/TestDisk
...though keep in mind that this is not guaranteed to work.
If you cannot do this, then it will be very difficult if not impossible to restore the Time Machine backup database in a usable fashion when the partition has been destroyed, as in order to do so you would need to restore a number of important files including all of their metadata that is often not possible to do with file restoration tools.
To get Time Machine running again your best bet would be to start fresh, though if you want to keep files from your lost Time Machine drive then you should use another one until you can scour this one and restore the files you've lost.