C++ में प्रत्येक ट्री पंक्ति में सबसे बड़ा मान ज्ञात करें

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, तो हमें उस पेड़ के प्रत्येक स्तर के सबसे बड़े तत्वों को खोजना होगा। तो अगर पेड़ जैसा है -

तब आउटपुट [3,5,8]

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

• एक सरणी परिभाषित करें जिसे उत्तर कहा जाता है

• एक पुनरावर्ती फ़ंक्शन को परिभाषित करें हल करें (), यह ट्री नोड लेगा, और स्तर, स्तर शुरू में 0 है। यह विधि इस तरह कार्य करेगी -

• यदि नोड शून्य है, तो वापस लौटें

• यदि स्तर =उत्तर का आकार, तो नोड मान को उत्तर में डालें, अन्यथा उत्तर [स्तर]:​​=अधिकतम उत्तर [स्तर] और नोड मान

• कॉल सॉल्व (नोड का लेफ्ट सबट्री, लेवल + 1)

• कॉल सॉल्व (नोड का राइट सबट्री, लेवल + 1)

• मुख्य विधि से, पैरामीटर के रूप में रूट का उपयोग करके हल () को कॉल करें, और स्तर =0

• फिर वापस आएं उत्तर

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

उदाहरण

#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:
   vector <int> ans;
   void solve(TreeNode* node, int level = 0){
      if(!node)return;
      if(level == ans.size()){
         ans.push_back(node->val);
      } else {
         ans[level] = max(ans[level], node->val);
      }
      solve(node->left, level + 1);
      solve(node->right, level + 1);
   }
   vector<int> largestValues(TreeNode* root) {
      solve(root);
      return ans;
   }
};
main(){
   vector<int> v = {1,3,2,5,3,NULL,9};
   TreeNode *tree = make_tree(v);
   Solution ob;
   print_vector(ob.largestValues(tree));
}

इनपुट

[1,3,2,5,3,null,9]

आउटपुट

[1, 3, 9, ]