ผลรวมทรีย่อยที่พบบ่อยที่สุดใน C++

สมมติว่าเรามีรากของต้นไม้ เราต้องหาผลรวมของทรีย่อยที่บ่อยที่สุด ผลรวมของทรีย่อยของโหนดคือผลรวมของค่าโหนดทั้งหมดที่เกิดขึ้นจากทรีย่อยที่รูทที่โหนดนั้น (รวมถึงตัวโหนดด้วย) ผลรวมทรีย่อยที่บ่อยที่สุดคือจริง ๆ แล้ว หากมีการเสมอกัน ให้คืนค่าทั้งหมดที่มีความถี่สูงสุดในลำดับใดๆ ดังนั้นถ้าต้นไม้เป็นเหมือน [5,2,-5] มันก็จะกลับมา [2] เนื่องจาก 2 เกิดขึ้นสองครั้ง อย่างไรก็ตาม -5 เกิดขึ้นเพียงครั้งเดียว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดสองแผนที่ m และความถี่ m คือชุดของคีย์จำนวนเต็มและรายการที่เกี่ยวข้อง และความถี่จะเก็บความถี่ของตัวเลขแต่ละตัว

• กำหนดวิธีการหนึ่งที่เรียกว่าแก้ปัญหา () ซึ่งจะใช้โหนดต้นไม้ ซึ่งจะทำหน้าที่ดังต่อไปนี้ −

• ถ้าโหนดเป็นโมฆะ ให้คืนค่า 0

• leftSum :=แก้ (ซ้ายของโหนด), rightSum :=แก้ไข (ทางขวาของโหนด)

• currSum :=ค่าโหนด + leftSum + rightSum

• หากการนับความถี่ไม่เหมือนกับ currSum แล้ว

  • แทรก currSum ลงในรายการปัจจุบันที่ m[1]

  • ตั้งค่าความถี่[currSum] :=1

• อย่างอื่น

  • เพิ่มความถี่[currSum] ขึ้น 1

  • แทรก currSum ลงในรายการปัจจุบันที่ m[freq[currSum]]

• คืนค่า currSum

• วิธีการหลักจะเป็นเช่น -

• หากรูทเป็นค่าว่าง ให้คืนค่าชุดว่าง

• แก้(ราก)

• กลับรายการสุดท้ายของแผนที่ 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, ]