Tìm cây con trùng lặp trong C++

Cho cây nhị phân, tìm tất cả các cây con trùng lặp (cấu trúc và giá trị giống nhau). Trả về gốc của mỗi nhóm cây con trùng lặp (chỉ một đại diện).

Thuật toán (Straight serialization + Hash Map)

1. Duyệt hậu tự (post-order), serialize mỗi cây con thành chuỗi: "val#left#right", node null → "-1".
2. Dùng map m đếm tần suất chuỗi.
3. Khi tần suất trở thành 2, thêm node hiện tại vào kết quả.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<TreeNode*> ret;
    map<string, int> m;
    string solve(TreeNode* node) {
        if (!node) return "-1";
        string x = to_string(node->val) + "#";
        string left = solve(node->left);
        string right = solve(node->right);
        x += "#" + left + "#" + right;
        m[x]++;
        if (m[x] == 2) ret.push_back(node);
        return x;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        ret.clear(); m.clear();
        solve(root);
        return ret;
    }
};

Ví dụ

Input: [1,2,3,4,null,2,4,null,null,null,null,4] → Output: các gốc của cây con [4] và [2,4].