# LeetCode Medium 652. Find Duplicate Subtrees

tags: leetcode

問題

• Explore
• Problems

アイデア

二分木が与えられたとき，全ての同じ構造の部分木を返せという問題です．

解法

• 連想配列を使います．
  • trees[あるノードの部分木] = あるノード
• helperという関数内関数を使って左部分木，右部分木に対して再帰的に関数を実行します．

計算量

木のノード数を$N$，深さを$H$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(H)$

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        trees = collections.defaultdict(list)
        def helper(node):
            if not node:
                return [None]
            left = helper(node.left)
            right = helper(node.right)
            values = left + right + [node.val]
            trees[tuple(values)].append(node)
            return values
        helper(root)
        return [trees[key][0] for key in trees if len(trees[key]) >= 2]