मान लीजिए हमारे पास एक बाइनरी ट्री है, यदि हम ट्री को दाईं ओर से देखते हैं, तो हम इसके कुछ एलिमेंट्स देख सकते हैं। हमें उन एलिमेंट्स को प्रदर्शित करना होगा। तो यदि ट्री इस तरह है −
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- हम dfs के लिए एक हेल्पिंग मेथड बनाएंगे। यह tree_node, उत्तरों को रखने के लिए एक ऐरे, और लेवल लेगा। लेवल प्रारंभ में 0 है। dfs नीचे की तरह काम करेगा −
- यदि नोड null है, तो लौटें
- यदि लेवल = उत्तर ऐरे की लंबाई, तो नोड के मान को ans ऐरे में डालें
- dfs(नोड का राइट, ans, लेवल + 1)
- dfs(नोड का लेफ्ट, ans, लेवल + 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, ]
