Over the years I've found 'PhotoRec' to be a reliable recovery utility but it might not be what you're looking for as it is a command-line tool, and it needs to be run on a computer/laptop:
https://en.wikipedia.org/wiki/PhotoRec
https://www.cgsecurity.org/wiki/PhotoRec
There are however plenty of viable recovery utilities with a graphical interface so hopefully others will reply with their recommendations.
But just some things to keep in mind:
-- Don't install a recovery app onto your Note 3, or any app for that matter, at least for now. Anything you do on your phone that writes data to the internal storage media can overwrite the some of your 'deleted' photos or videos. The less you use your Note 3, the better chance you have recovering those files.
-- Any good file recovery utility will take a good amount of time to run. It's not like searching through a folder with a lot of files in it, a recovery utility is working at a much deeper level. It's scanning the storage media on a block-by-block basis, looking for data that matches recognizable file types that (in a very rough analogy) have been flagged as 'deleted'.
-- If you don't have access to a computer/laptop and have to opt with a recovery app, be sure to point the source location for recovered files to your Note's microSD card. Again, it's important to limit anything saved to the internal storage media as that can possibly overwrite some of those files you want to recover.
-- Once you get past this recovery process, give serious thought to installing something like the Google Photos app. It includes a really important backup & sync function so your photos and videos get automatically backed up into your online Google account. (When you install the app be sure to go into its Settings menu to enable the options you need.)
https://play.google.com/store/apps/details?id=com.google.android.apps.photos&hl=en
If you have a large photo library the initial upload could take some time (especially with videos) but once done, even if you don't have your phone with you, just go to
https://photos.google.com to access your photo library online.
