C++에서 가장 자주 사용되는 하위 트리 합계

트리의 루트가 있다고 가정하고 가장 빈번한 하위 트리 합계를 찾아야 합니다. 노드의 하위 트리 합계는 실제로 해당 노드(노드 자체 포함)를 기반으로 하는 하위 트리에 의해 형성된 모든 노드 값의 합계입니다. 가장 빈번한 하위 트리 합계는 실제로 동률이 있는 경우 빈도가 가장 높은 모든 값을 임의의 순서로 반환합니다. 따라서 트리가 [5,2,-5]와 같으면 [2]를 반환합니다. 2는 두 번 발생하지만 -5는 한 번만 발생하기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 두 개의 맵 m과 freq를 정의하고 m은 정수 키와 해당 목록의 집합이며 freq는 각 숫자의 빈도를 저장합니다.

• solve()라는 메소드를 정의하면 트리 노드가 사용됩니다. 이것은 다음과 같이 작동합니다 -

• 노드가 null이면 0을 반환합니다.

• leftSum :=solve(노드의 왼쪽), rightSum :=solve(노드의 오른쪽)

• currSum :=노드 값 + leftSum + rightSum

• 빈도 수가 currSum과 같지 않으면

  • m[1]에 있는 목록에 currSum을 삽입하십시오.

  • 설정 주파수[currSum] :=1

• 그렇지 않으면

  • freq[currSum] 1 증가

  • m[freq[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, ]