def findDuplicateSubtrees(self, root):
def trv(root):
if not root: return "null"
struct = "%s,%s,%s" % (str(root.val), trv(root.left), trv(root.right))
nodes[struct].append(root)
return struct
nodes = collections.defaultdict(list)
trv(root)
return [nodes[struct][0] for struct in nodes if len(nodes[struct]) > 1]
Python easy understand solution


@samaryadav5
I used a preorder traversal and each traversal funcitontrv
wil return the the values of subtree. Then I saved the the subtree as a key in the hashmapnodes
. Finally I returned the first node for every key in thenodes
if there are at least 2 values.

@RunRunCode
You can do it in any order.
If a node is None, it will also be noted. So it does work for a general binary tree.

People in another thread has found out it won't work for inorder. https://discuss.leetcode.com/topic/97584/javaconcisepostordertraversalsolution/29
And documenting the None node doesn't mean it can uniquely represent a general tree structure IMHO. (I feel like it works, but not convinced yet.)

@RunRunCode
Yes inorder doesn't work as it mentioned in another thread.
However preoder works. When you construct the tree in preorder, you know exactly where you start  root. Then you will go to current node's children unless you meet two "null". As you can see, the tree constructed is unique.