Tổng cây con thường xuyên nhất trong C ++

Giả sử chúng ta có gốc của một cây, chúng ta phải tìm tổng của cây con thường xuyên nhất. Tổng cây con của một nút thực sự là tổng của tất cả các giá trị nút được tạo thành bởi cây con bắt nguồn từ nút đó (bao gồm cả chính nút đó). Tổng của cây con thường xuyên nhất thực sự là Nếu có sự ràng buộc, hãy trả về tất cả các giá trị có tần suất cao nhất theo bất kỳ thứ tự nào. Vì vậy, nếu cây giống như [5,2, -5], thì nó sẽ trả về [2]. Điều này là do 2 xảy ra hai lần, tuy nhiên -5 chỉ xảy ra một lần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định hai bản đồ m và freq, m là tập hợp các khóa số nguyên và một danh sách tương ứng và freq sẽ lưu trữ tần suất của mỗi số.

• xác định một phương thức gọi là giải quyết (), phương thức này sẽ lấy nút cây. Điều này sẽ hoạt động như sau -

• nếu nút là null, thì trả về 0

• leftSum:=giải quyết (bên trái của nút), rightSum:=giải quyết (bên phải của nút)

• currSum:=node value + leftSum + rightSum

• nếu số lượng tần suất không giống như currSum, thì

  • chèn currSum vào danh sách hiện có tại m [1]

  • đặt freq [currSum]:=1

• nếu không thì

  • tăng freq [currSum] lên 1

  • chèn currSum vào danh sách có tại m [freq [currSum]]

• trả về currSum

• Phương thức chính sẽ giống như -

• nếu gốc là null, thì trả về tập hợp rỗng

• giải quyết (root)

• trả lại danh sách cuối cùng của bản đồ m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[5,2,-5]

Đầu ra

[2, ]