หา Subtree ซ้ำในต้นไม้แบบทวิภาคใน C++

ให้ต้นไม้แบบทวิภาค ต้องการหา subtree ที่ซ้ำกันทั้งหมด สำหรับแต่ละประเภทของ subtree ที่ซ้ำ ให้คืน root node ของตัวแทนหนึ่งตัว

ตัวอย่าง: ต้นไม้ที่มีโครงสร้างซ้ำกัน จะได้ subtree ซ้ำ 2 แบบ

วิธีแก้ปัญหา (Tree Serialization + Hash Map)

1. สร้างอาร์เรย์ ret เก็บผลลัพธ์ และ map m นับจำนวน
2. สร้างฟังก์ชันเวียนเกิด solve(node):
   • ถ้า node เป็น null → คืน "-1"
   • x = ค่า node + "#"
   • left = solve(left child), right = solve(right child)
   • x = x + "#" + left + "#" + right (serialize subtree)
   • เพิ่ม m[x] ขึ้น 1
   • ถ้า m[x] == 2 → ใส่ node ลง ret
   • คืน x
3. จาก main เรียก solve(root) แล้วคืน ret

ตัวอย่างโค้ด C++

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

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

class Solution {
public:
    vector<TreeNode*> ret;
    map<string, int> m;
    
    string solve(TreeNode* node) {
        if (!node || node->val == 0) return "-1";
        string x = to_string(node->val);
        x += "#";
        string left = solve(node->left);
        string right = solve(node->right);
        x = 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;
    }
};

int main() {
    // ตัวอย่างการทดสอบ
    return 0;
}

Input

[1,2,3,4,null,2,4,null,null,null,null,4]

Output

[4, ] [2, 4, ]