Find Duplicate Subtrees

바이너리 트리의 루트 노드를 받고 해당 트리에서

구조와 값이 동일한 서브 트리들을 찾아 벡터에 넣어 반환하는 문제

/**
 * 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:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        
        unordered_map<string, pair<int, TreeNode*>> trees{};

        SearchDFS(root, trees);

        vector<TreeNode*> result{};

        for (auto& [structure, pairs] : trees)
        {
            if (1 < pairs.first)
            {
                result.push_back(pairs.second);
            }
        }

        return result;
    }
private:
    string SearchDFS(TreeNode* node, unordered_map<string, pair<int, TreeNode*>>& trees)
    {
        string structure{to_string(node->val) + ","};

        if (node->left)
        {
            structure += SearchDFS(node->left, trees);
        }
        else
        {
            structure += ",";
        }

        if (node->right)
        {
            structure += SearchDFS(node->right, trees);
        }
        else
        {
            structure += ",";
        }

        if (trees.count(structure) == 0)
        {
            trees[structure] = {1, node};
        }
        else
        {
            ++(trees[structure].first);
        }

        return structure;
    }
};