dyld: Library not loaded: /usr/local/opt/icu4c/lib/libicui18n.62.dylib error running php after installing node with brew on Mac

I installed node using homebrew (Mojave), afterwards php stoped working and if I try to run php -v I get this error:

php -v
dyld: Library not loaded: /usr/local/opt/icu4c/lib/libicui18n.62.dylib
  Referenced from: /usr/local/bin/php
  Reason: image not found

I tried to uninstall both node and icu4c but the problem persists

Update - As stated in some of the comments, running brew cleanup could possibly fix this error, if that alone doesn't fix it, you might try upgrading individual packages or all your brew packages.

I just had this same problem. Upgrading Homebrew and then cleaning up worked for me. This error likely showed up for me because of a mismatch in package versions. None of the above solutions resolved my error, but running the following homebrew commands did.

Caution - This will upgrade all your brew packages, including, but not limited to PHP. If you only want to upgrade specific packages make sure to be specific.

brew upgrade icu4c

brew upgrade // or upgrade all packages

and finally

brew cleanup