C ++中最常见的子树总和

假设我们有一棵树的根，我们必须找到最频繁的子树总和。节点的子树总和实际上是由植根于该节点的子树（包括节点本身）形成的所有节点值的总和。实际上，最频繁的子树总和是如果存在平局，则以任意顺序返回频率最高的所有值。因此，如果树类似于[5,2，-5]，则它将返回[2]。这是因为2发生两次，但是-5仅发生一次。

为了解决这个问题，我们将遵循以下步骤-

• 定义两个映射m和freq，m是一组整数键和一个对应的列表，freq将存储每个数字的频率。

• 定义一个称为的方法solve()，它将采用树节点。这将如下所示-

• 如果node为null，则返回0

• leftSum：= Solve（节点的左边），rightSum：= Solve（节点的右边）

• currSum：=节点值+ leftSum + rightSum

• 如果频率计数与currSum不同，则

• 将currSum插入到m [1]处的列表中

• 设置freq [currSum]：= 1

• 除此以外

• 将freq [currSum]增加1

• 将currSum插入存在于m [freq [currSum]]的列表中

• 返回currSum

• 主要方法将是-

• 如果root为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, ]