I permanently deleted notes on my iPhone because I bought a new iPhone but they were also deleted on my new device. Is there any way I can recover those notes I really need them

If it is not in Recently deleted folder then you have not deleted any Notes in last 30 days.

You may have moved it in other accounts.

• Check your email accounts that you had but removed. Because many of the accounts have notes synced like Google, iCloud, AOL, Exchange, Outlook, Yahoo etc.

You can't find it in the recently deleted folder, then probably you have not deleted any Notes in last 30 days.

(See the Pic below)

Though restore from backup is an option but you need to restore the entire iPhone (only Notes restoration option does not exists) including all apps, Photos, Videos, Voice Memos, Notes on your iPhone etc...

The question is when did you backup and when did you delete...Read on...

Date1 : Backup date

Date2 : Notes Deletion Date

Date3 : Current Date / Restore Date

Given that --> Date1 < Date2 < Date3 

Risk of restoring on Date3: You may lose data between the Date1 & Date 3

Mitigation: Create Multiple backup on iTunes for the same device. (By default iTunes creates incremental backup over the existing backup such that you only will have one backup per device on iTunes)

How to create Multiple Backup for the same device.

1. On iTunes Click on Manage Backups
2. Right Click on a Backup and Click Archive
3. Click Backup Now.
4. You will see a fresh backup will get created See the GIF below

1. Restore from Backup dated Date1 (Archived)
2. Retrieve the Notes and store it separately
3. Restore from Current Backup Date3

The above GIF can also be viewed as a Video here --> https://youtu.be/LOPkFPgIPnw