C++ में बाइनरी ट्री राइट साइड व्यू

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

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

• हम dfs के लिए एक हेल्पिंग मेथड बनाएंगे। यह ट्री_नोड, उत्तर रखने के लिए एक सरणी और स्तर लेगा। स्तर शुरू में 0 है। dfs नीचे की तरह काम करेगा -
• यदि नोड शून्य है, तो वापस आएं
• यदि स्तर =उत्तर सरणी की लंबाई, तो उत्तर सरणी में नोड का मान डालें
• dfs(नोड के दाईं ओर, उत्तर, स्तर + 1)
• dfs(नोड के बाएं, उत्तर, स्तर + 1)
• मुख्य फ़ंक्शन से dfs() को पेड़ की जड़ और एक रिक्त सरणी का उपयोग करके कॉल करें, प्रारंभ में स्तर 0 है, इसलिए यह dfs(root, ans) होगा

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> 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 = 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:
   void dfs(TreeNode* node, vector <int>& ans, int level = 0){
      if(!node) return;
      if(level == ans.size())ans.push_back(node->val);
      dfs(node->right, ans, level + 1);
      dfs(node->left, ans, level + 1);
   }
   vector<int> rightSideView(TreeNode* root) {
      vector <int> ans;
      dfs(root, ans);
      return ans;
   }
};
main(){
   vector<int> v = {1,2,3,NULL,5,NULL,4};
   TreeNode *root = make_tree(v);
   Solution ob;
   print_vector(ob.rightSideView(root));
}

इनपुट

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

आउटपुट

[1, 3, 4, ]