Python easy understand solution


  • 8
    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]

  • 0
    S

    Thanks for sharing. Can you please add some explanation.


  • 0

    @samaryadav5
    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.


  • 0

    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.


  • 0

    @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.


  • 0

    @lee215

    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.)


  • 0

    @RunRunCode
    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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.