पेड़ के स्तर को खोजने के लिए कार्यक्रम जिसमें सी ++ में न्यूनतम योग है

मान लीजिए हमारे पास एक बाइनरी ट्री है, इसकी जड़ का स्तर 1 है, इसके बच्चों का स्तर 2 है, और इसी तरह। हमें सबसे छोटा स्तर X खोजना है जैसे कि स्तर X पर नोड्स के सभी मानों का योग न्यूनतम हो। तो अगर पेड़ जैसा है -

आउटपुट 2 होगा क्योंकि योग 4 - 10 =-6 है, जो न्यूनतम है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

स्तर:=1, योग:=आर का मूल्य, उत्तर स्तर:=स्तर, उत्तर योग:=योग
एक कतार q परिभाषित करें, दिए गए नोड r को q में डालें
जबकि q खाली नहीं है
- क्षमता :=q का आकार
- स्तर 1 से बढ़ाएँ, योग :=0
- जबकि क्षमता 0 नहीं है
  - नोड:=q से सामने वाला नोड, q से नोड हटाएं
  - यदि नोड का अधिकार मान्य है, तो योग:=योग + दाएँ नोड का मान, दाएँ सम्मिलित करें
  - क्यू में नोड
  - यदि नोड का बायां नोड मान्य है, तो योग:=योग + बाएं नोड का मान, बाएं नोड को q में डालें
  - क्षमता में 1
    . की कमी करें
- अगर ansSum <योग, तो ansSum:=sum, ansLevel:=level
उत्तर स्तर पर लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें-

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
      right = NULL;
      }
};
class Solution {
   public:
   int solve(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(){
   TreeNode *root = new TreeNode(5);
   root->left = new TreeNode(4);
   root->right = new TreeNode(-10);
   root->left->right = new TreeNode(-2);
   root->right->left = new TreeNode(-7);
   root->right->right = new TreeNode(15);
   Solution ob;
   cout <<ob.solve(root);
}

इनपुट

TreeNode *root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(-10);
root->left->right = new TreeNode(-2);
root->right->left = new TreeNode(-7);
root->right->right = new TreeNode(15);