Why use a Map instead of a Set for this?

I do prefer this to using the clone() method, as you'll be reminded
when writing recursive deepCopy() methods that there's no deepCopy()
on List, etc.; writing a recursive clone() method you may well
unthinkingly invoke clone() on a collection and get a shallow copy
instead of a won't compile as a result. Obvious bugs are better than
subtle bugs, especially ones that may initially be completely silent.

You also don't need to copy Strings and other value objects that are
not mutated, unless there's a need for the original and the copy of
the value object to compare != for some reason. Otherwise just copy
the reference.

Mutable objects that are semantically-constant might also not need
copying. (E.g. a protocol handler object that is stateful, but where
this is logically always the same object and it makes sense for both
copies of your larger structure to share the same one rather than use
two separate ones.)

Careful, clone doesn't do a deep copy automatically.
All the objects you clone will have a shallow copy only, unless you
override the clone method.

If you have any immutable objects in the tree, they likely don't need
to be duplicated.