# Leetcode 652. Find Duplicate Subtrees
###### tags: `leetcode` `daily` `DFS`

[題目連結](https://leetcode.com/problems/find-duplicate-subtrees/description/)

題目說明:
給一個binary tree, 找出所有重複的subtrees.

# Method DFS
:::info
:bulb: **中文作法說明**:
對於這個題目, 關鍵在於 如何定義重複的子樹, 以及有效率的方式找到重複的子樹.

**定義重複的子數: 可以透過序列化的方式 將subtree變成字串.**
**有效率的方式找到重複的子樹: 可以透過hash_map, key = string.**

我們可以使用DFS的方式, 依序尋訪每個節點,
尋訪到每個節點 先把 "val" 變成字串,
蒐集左邊節點的字串, 蒐集右邊節點的字串,
將這三個字串 連接起來 就變成該節點的字串.
把這個字串當成key, node pointer當成value hash_map裡面.

最後只要尋訪所有的key, 只要node pointer 的數量 大於 1
表示有重複的子樹.

:::

:::info
:bulb: **英文作法說明**:
## key point:
**define duplicate subtree:** using serialize, tranform subtree into string.
**find the duplicate subtree efficiency:** using hash_map, key is string, value is node pointer

we can use DFS algorithm, scan all of the node,

for each node,
transform "val" to string,
get the string of left child node,
get the string of right child node,
concatenate these three strings and define the resuting string is "s".
put "s" and node pointer into hash_map.

after scan all of the node,
we can scan hash_map,
if the value, node pointer size is bigger than 1,
we can say the subtree is duplicate.
:::

TC: O(N^2) SC: O(N^2)
:::spoiler 完整程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string dfs(TreeNode* root, unordered_map<string, vector<TreeNode*>> &m) {
        if(root == NULL) {
            return ".N";
        }
        string s = "." + to_string(root->val);
        s += dfs(root->left, m);
        s += dfs(root->right, m);
        m[s].push_back(root);

        return s;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, vector<TreeNode*>> m;
        vector<TreeNode*> output;
        dfs(root, m);
        for(auto &[s, v] : m) {
            if(v.size() > 1) {
                output.push_back(v[0]);
            }
        }
        return output;
    }
};

:::