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] for struct in nodes if len(nodes[struct]) > 1]
I used a preorder traversal and each traversal funciton
trv wil return the the values of subtree. Then I saved the the subtree as a key in the hashmap
nodes. Finally I returned the first node for every key in the
nodes if there are at least 2 values.
Why preorder will be sufficient to represent a unique tree structure? Theoretically, preorder is only sufficient to reconstruct a BST, but not a general binary tree.
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 in-order. https://discuss.leetcode.com/topic/97584/java-concise-postorder-traversal-solution/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.)
Yes in-order doesn't work as it mentioned in another thread.
However pre-oder works. When you construct the tree in pre-order, 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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.