C++ में बाइनरी ट्री का अधिकतम लेवल सम

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

तो आउटपुट 2 होगा, लेवल 1 का योग = 1, लेवल 2 का योग 7 + 0 = 7 है, लेवल 3 का योग 7 + (-8) = -1 है, इसलिए मैक्स लेवल 2 का है, इसलिए आउटपुट 2 है।

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

लेवल := 1, सम := r का मान, ansLevel := लेवल, ansSum := सम
एक क्यू q परिभाषित करें, दिए गए नोड r को q में डालें
जब तक q खाली नहीं है
- कैपेसिटी := q का आकार
- लेवल को 1 से बढ़ाएं, सम := 0
- जब तक कैपेसिटी 0 नहीं है
  - नोड := q से फ्रंट नोड, q से नोड डिलीट करें
  - यदि नोड का राइट वैध है, तो सम := सम + राइट नोड का मान, राइट नोड को q में डालें
  - यदि नोड का लेफ्ट वैध है, तो सम := सम + लेफ्ट नोड का मान, लेफ्ट नोड को q में डालें
  - कैपेसिटी को 1 से घटाएं
- यदि ansSum < सम, तो ansSum := सम, ansLevel := लेवल
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]