652.Find Duplicate Subtrees
===

###### tags: `Medium`,`DFS`,`Binary Tree`,`Tree`,`Hash Table`

[652. Find Duplicate Subtrees](https://leetcode.com/problems/find-duplicate-subtrees/)

### 題目描述

Given the `root` of a binary tree, return all **duplicate subtrees**.

For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are **duplicate** if they have the **same structure** with the **same node values**.

### 範例

**Example 1:**


Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

**Example 2:**


Input: root = [2,1,1]
Output: [[1]]

**Example 3:**


Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

**Constraints**:

* The number of the nodes in the tree will be in the range `[1, 5000]`
* -200 <= `Node.val` <= 200

### 解答
#### C++

class Solution {
public:
    unordered_map<string, int> count;
    vector<TreeNode*> ans;

    string encode(TreeNode* node) {
        if (!node) return "";
        string key = to_string(node->val) + ","
                     + encode(node->left) + ","
                     + encode(node->right);
        if (count[key]++ == 1) ans.push_back(node);
        return key;
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        encode(root);
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Tue, Feb 28, 2023]

#### Python

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        ans = []
        counter = defaultdict(int)

        def encode(node):
            if not node: return ''
            key = str(node.val) + ',' \
                  + encode(node.left) + ',' \
                  + encode(node.right)
            counter[key] += 1
            if counter[key] == 2:
                ans.append(node)
            return key
        
        encode(root)
        return ans

> [name=Yen-Chi Chen][time=Tue, Feb 28, 2023]

Time: $O(n)$
Extra Space: $O(n^2)$ 儲存每顆樹的序列string

> [name=XD] [time= Feb 28, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)