CODEWITHSUNDEEP
pythonrecursionbinary-tree
Dawn17
Dawn17

Reputation: 8297

Not sure how this recursion works

class Solution: 
    def findDuplicateSubtrees(self, root):
        self.res = []
        self.dic = {}
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root: return '#'
        tree = self.dfs(root.left) + self.dfs(root.right) + str(root.val)

        if tree in self.dic and self.dic[tree] == 1:
            self.res.append(root)
        self.dic[tree] = self.dic.get(tree, 0) + 1

        return tree

This is a solution for getting all duplicate subtrees given a binary tree. I am not sure what tree = self.dfs(root.left) + self.dfs(root.right) + str(root.val) is trying to give.

I know it's trying to do a postorder traversal, but how does this part actually work?

It would be great if anyone can follow through this code. Thanks.

Upvotes: 0

Views: 41

Answers (2)

lincr
lincr

Reputation: 1653

Basically, the variable tree can be regarded as an encoding string for each subtree. And we use a global dict self.dic to memorize those encoded strings.

An examples:

     A
  B      C
D   D  E   B
          D  D

In level order, the binary tree can be descripted as [[A], [B, C], [D, D, E, B], [#, #, #, #, #, #, D, D]], so we have at least two duplicate subtrees as [[B], [D, D]] and [D] Follow the code, we have

dfs(A)
  dfs(B)
    dfs(D) *save ##D, return ##D
    dfs(D) *find ##D, get one subtree, return ##D
  *save ##D##DB, return ##D##DB
  dfs(C)
  ...

Upvotes: 1

Amadan
Amadan

Reputation: 198324

Recursion is best untangled from bottom up.

  • A non-node (a daughter of a leaf node) will return "#".
  • A leaf with value 1 would return "##1" (as it has two non-node children).
  • A node 3 with two leaf daughters 1 and 2 would return ##1##23. "##1" is the dfs of the left daughter, "##2" is the dfs of the right daughter, and "3" is the stringified current node's value.

In this way, assuming there's no node with value 23 and another with empty string value, you can see that if two different nodes produce ##1##23, they are a duplicate subtree. It would be much more robust if there were some additional separators employed (e.g. a semicolon at the end of that line would produce "##1;##2;3;), which would be sufficient to make it a bit more readable and less ambiguous. Even safer (but slower) if done with lists.

Upvotes: 1

Related Questions