Approach #1: DepthFirst Search [Accepted]
Intuition
We can serialize each subtree. For example, the tree
1 / \ 2 3 / \ 4 5
can be represented as the serialization 1,2,#,#,3,4,#,#,5,#,#
, which is a unique representation of the tree.
Algorithm
Perform a depthfirst search, where the recursive function returns the serialization of the tree. At each node, record the result in a map, and analyze the map after to determine duplicate subtrees.
Complexity Analysis

Time Complexity: , where is the number of nodes in the tree. We visit each node once, but each creation of
serial
may take work. 
Space Complexity: , the size of
count
.
Approach #2: Unique Identifier [Accepted]
Intuition
Suppose we have a unique identifier for subtrees: two subtrees are the same if and only if they have the same id.
Then, for a node with left child id of x
and right child id of y
, (node.val, x, y)
uniquely determines the tree.
Algorithm
If we have seen the triple (node.val, x, y)
before, we can use the identifier we've remembered. Otherwise, we'll create a new one.
Complexity Analysis

Time Complexity: , where is the number of nodes in the tree. We visit each node once.

Space Complexity: . Every structure we use is using storage per node.
Analysis written by: @awice. Approach #2 inspired by @StefanPochmann.