C++-এ বাইনারি ট্রির সর্বোচ্চ লেভেল সম

মনে করুন একটি বাইনারি ট্রির রুট `r` দেওয়া আছে, এর রুটের লেভেল ১, এর চাইল্ডের লেভেল ২, এবং এভাবেই চলবে। আমাদের সবচেয়ে ছোট লেভেল `X` রিটার্ন করতে হবে যাতে লেভেল `X`-এ সব নোডের ভ্যালুর যোগফল সর্বোচ্চ। যদি ট্রি নিচের মোতাবিক হয় -

তবে আউটপুট হবে ২, লেভেল ১ সম = ১, লেভেল ২ সম = 7 + 0 = 7, লেভেল ৩ সম = 7 + (-8) = -1, তাই সর্বোচ্চ লেভেল ২, আউটপুট ২।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

`level := 1`, `sum := r`-এর মান, `ansLevel := level`, `ansSum := sum`
একটি কিউ `q` সংজ্ঞায়িত করুন, দেওয়া নোড `r`-কে `q`-তে ইনসার্ট করুন
যখন `q` খালি না থাকে
- `capacity := q`-এর আকার
- `level` ১ বাড়ান, `sum := 0`
- যখন `capacity` ০ না হয়
  - `node := q`-এর ফ্রন্ট নোড, `q`-থেকে নোড ডিলিট করুন
  - যদি `node`-এর ডান বৈধ থাকে, তবে `sum := sum + node`-এর ডান মান, `node`-এর ডান `q`-তে ইনসার্ট করুন
  - যদি `node`-এর বাম বৈধ থাকে, তবে `sum := sum + node`-এর বাম মান, `node`-এর বাম `q`-তে ইনসার্ট করুন
  - `capacity` ১ কমান
- যদি `ansSum < sum`, তবে `ansSum := sum`, `ansLevel := level`
`ansLevel` রিটার্ন করুন

উদাহরণ (C++)

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -

#include <bits/stdc++.h> using namespace std; 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:    int maxLevelSum(TreeNode* r) {       int level = 1, sum = r->val;       int ansLevel = level, ansSum = sum;       queue <TreeNode*> q;       q.push(r);       while(!q.empty()){          int capacity = q.size();          level++;          sum = 0;          while(capacity--){             TreeNode* node = q.front();             q.pop();             if(node->right){                sum += node->right->val;                q.push(node->right);             }             if(node->left){                sum += node->left->val;                q.push(node->left);             }          }          if(ansSum<sum){             ansSum = sum;             ansLevel = level;          }       }       return ansLevel;    } }; main(){    vector<int> v = {1,7,0,7,-8,NULL,NULL};    TreeNode *root = make_tree(v);    Solution ob;    cout <<ob.maxLevelSum(root); }

ইনপুট

[1,7,0,7,-8,null,null]