ผลรวมต้นไม้ย่อยที่พบบ่อยที่สุด (Most Frequent Subtree Sum) ใน C++

ผลรวมต้นไม้ย่อยที่พบบ่อยที่สุด (Most Frequent Subtree Sum)

ผลรวมต้นไม้ย่อย (subtree sum) ของโหนดคือผลรวมค่าของโหนดทั้งหมดในต้นไม้ย่อยที่รากคือโหนดนั้น (รวมตัวมันเอง) หาผลรวมที่เกิดบ่อยที่สุด ถ้ามีหลายค่าเท่ากัน ให้คืนค่าทั้งหมด

ตัวอย่าง: [5,2,-5] → ผลรวม: 5+2-5=2 (ราก), 2 (ลูกซ้าย), -5 (ลูกขวา) → 2 เกิด 2 ครั้ง คืนค่า [2]

ขั้นตอนการแก้ปัญหา (DFS + Hash Map)

1. ใช้ unordered_map<int, int> freq นับความถี่แต่ละผลรวม
2. ฟังก์ชัน dfs(node) คืนค่า subtree sum:
   • ถ้า node == null คืนค่า 0
   • left = dfs(node.left), right = dfs(node.right)
   • sum = node.val + left + right
   • freq[sum]++
   • คืนค่า sum
3. หลัง DFS เสร็จ หาความถี่สูงสุด maxFreq
4. รวบรวมผลรวมที่มีความถี่เท่ากับ maxFreq

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

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

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

class Solution {
public:
    unordered_map<int, int> freq;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int sum = node->val + dfs(node->left) + dfs(node->right);
        freq[sum]++;
        return sum;
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        freq.clear();
        dfs(root);
        int maxFreq = 0;
        for (auto& p : freq) maxFreq = max(maxFreq, p.second);
        vector<int> res;
        for (auto& p : freq) if (p.second == maxFreq) res.push_back(p.first);
        return res;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [5,2,-5]

Output: [2]