C++で最も頻繁に使用されるサブツリーの合計

ツリーのルートがあるとすると、最も頻繁なサブツリーの合計を見つける必要があります。ノードのサブツリーの合計は、実際には、そのノードをルートとするサブツリー（ノード自体を含む）によって形成されるすべてのノード値の合計です。最も頻度の高いサブツリーの合計は、実際には次のとおりです。同点の場合は、頻度が最も高いすべての値を任意の順序で返します。したがって、ツリーが[5,2、-5]のような場合、[2]を返します。これは、2が2回発生するが、-5は1回しか発生しないためです。

これを解決するには、次の手順に従います-

• 2つのマップmとfreqを定義します。mは整数キーと対応するリストのセットであり、freqは各数値の頻度を格納します。

• Solve（）と呼ばれる1つのメソッドを定義します。これにより、ツリーノードが取得されます。これは次のように機能します-

• ノードがnullの場合、0を返します

• leftSum：=solve（ノードの左側）、rightSum：=solve（ノードの右側）

• currSum：=ノード値+ leftSum + rightSum

• 頻度カウントがcurrSumと同じでない場合は、

  • m [1]

    にあるリストにcurrSumを挿入します

  • set freq [currSum]：=1

• それ以外の場合

  • freq[currSum]を1増やします

  • m [freq [currSum]]

    にあるリストにcurrSumを挿入します

• currSumを返す

• 主な方法は次のようになります-

• ルートがnullの場合、空のセットを返します

• 解決（ルート）

• マップ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, ]