Find Duplicate Subtrees

LeetCode 652

from collections import Counter
class Solution:
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
                1
               / \
              2   3
             /   / \
            4   2   4
               /
              4
        使用 post-order dfs 以每個node為記錄點紀錄子樹構成
        若不用Counter()而只用dictionary的話要注意 key error問題
        dict[strr] = dict.get(strr,0) + 1
        """
        counter = Counter()
        res = []
        def dfs(root):
            if not root:
                return '#'         
            strr = dfs(root.left) + dfs(root.right) + str(root.val)
            if counter[strr] == 1:
                res.append(root)
            counter[strr] +=1
            return strr
        
        dfs(root)
        return res