C++で最も頻出する部分木の合計を求めるアルゴリズム

木のルートが与えられたとき、最も頻繁に出現する「部分木の合計」を求める問題を考えてみましょう。あるノードにおける部分木の合計とは、そのノードを根とする部分木に含まれるすべてのノード値（そのノード自身を含む）の総和のことです。最頻出の部分木の合計が複数あり同率となった場合は、どのような順序でもよいので、最大頻度を持つすべての値を返します。

たとえば、木が [5,2,-5] で構成されている場合、答えは [2] となります。これは、葉ノード 2 の合計値と、根 5 の部分木全体の合計値（5 + 2 + (-5) = 2）が一致して 2 が 2 回出現する一方、-5 は 1 回しか出現しないためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• 2つのマップ m と freq を定義します。m は整数キーとそれに対応するリストの集合を保持し、freq は各数値の出現回数を記録します。
• 木のノードを受け取る solve() メソッドを定義します。このメソッドは以下のように動作します。
• ノードが NULL の場合は 0 を返します。
• leftSum := solve(ノードの左の子)、rightSum := solve(ノードの右の子) を再帰的に計算します。
• currSum := ノードの値 + leftSum + rightSum とします。
• freq に currSum がまだ存在しない場合は、m[1] のリストに currSum を挿入し、freq[currSum] := 1 を設定します。
• すでに存在する場合は、freq[currSum] を 1 増やし、m[freq[currSum]] のリストに currSum を挿入します。
• 最後に currSum を返します。

メインの処理は以下の流れになります。

• ルートが NULL の場合は空の集合を返します。
• solve(root) を呼び出して全ノードを走査します。
• マップ m の最後（最大頻度）のリストを結果として返します。

マップ m はキーが出現回数、値がその回数で出現した合計値のリストとなるため、最後に登録されたキー（最高頻度）に対応するリストを取得すれば答えが得られます。理解を深めるために、以下の実装例を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   map <int, vector <int> > m;
   map <int, int > freq;
   int solve(TreeNode* node){
      if(!node)return 0;
      int leftSum = solve(node->left);
      int rightSum = solve(node->right);
      int currSum = node->val + leftSum + rightSum;
      //cout << currSum << endl;
      if(!freq.count(currSum)){
         m[1].push_back(currSum);
         freq[currSum] = 1;
         //cout << "Adding " << currSum << " 1" << endl;
      } else {
         freq[currSum]++;
         m[freq[currSum]].push_back(currSum);
      }
      return currSum;
   }
   vector<int> findFrequentTreeSum(TreeNode* root) {
      m.clear();
      freq.clear();
      if(!root)return {};
      solve(root);
      return m.rbegin()->second;
   }
};
main(){
   vector<int> v = {5,2,-5};
   TreeNode *tree = make_tree(v);
   Solution ob;
   print_vector(ob.findFrequentTreeSum(tree));
}

入力

[5,2,-5]

出力

[2]