C++ में बाइनरी ट्री के पत्ते खोजें

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हम सभी पत्तियों को इकट्ठा करके हटा देंगे और पेड़ के खाली होने तक दोहराएंगे।

तो, अगर इनपुट पसंद है

तो आउटपुट [[4,5,3],[2],[1]]

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

• एक नक्शा sz परिभाषित करें

• एक 2डी सरणी रेट परिभाषित करें

• फ़ंक्शन को परिभाषित करें dfs(), यह नोड लेगा,

• यदि नोड शून्य है, तो -

  • sz[नोड का वैल] :=1 + अधिकतम dfs (नोड के बाएँ) और dfs (नोड के दाएँ)

• यदि रिट का आकार

  • एक सरणी अस्थायी परिभाषित करें

  • रिट के अंत में अस्थायी डालें

• रिट के अंत में नोड का वैल डालें [sz [नोड का वैल] - 1]

• वापसी sz [नोड का वैल]

• मुख्य विधि से, निम्न कार्य करें -

• dfs(रूट)

• वापसी रिट

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto< > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   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:
   unordered_map <int, int> sz;
   vector < vector <int< > ret;
   int dfs(TreeNode* node){
      if(!node) return 0;
         sz[node->val] = 1 + max(dfs(node->left), dfs(node->right));
      if(ret.size() < sz[node->val]){
         vector <int< temp;
         ret.push_back(temp);
      }
      ret[sz[node->val] - 1].push_back(node->val);
      return sz[node->val];
   }
   vector<vector<int<> findLeaves(TreeNode* root) {
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int< v = {1,2,3,4,5};
   TreeNode *root = make_tree(v);
   print_vector(ob.findLeaves(root));
}

इनपुट

{1,2,3,4,5}

आउटपुट

[[3, 5, 4, ],[2, ],[1, ],]