मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें इसके सीमा के मानों को रूट से शुरू करके वामावर्त दिशा में ढूंढना है। यहां सीमा में बायां सीमा, पत्ते, और दायां सीमा क्रम में बिना डुप्लिकेट नोड्स के शामिल हैं।
- बायां सीमा रूट से बाएं-सबसे नोड तक का पथ है।
- दायां सीमा रूट से दाएं-सबसे नोड तक का पथ है।
- जब रूट का बायां उपट्री या दायां उपट्री नहीं होता है, तो रूट स्वयं बायां सीमा या दायां सीमा होता है।
उदाहरण के लिए, यदि इनपुट दिए गए चित्र के अनुसार है, तो आउटपुट [1,2,4,7,8,9,10,6,3] होगा।
हल करने की विधि
हम तीन अलग-अलग ट्रैवर्सल का उपयोग करेंगे:
- परिणाम सरणी ret परिभाषित करें।
leftBoundary(): नोड null या लीफ है तो लौटें; मान जोड़ें; बाएं बच्चे को प्राथमिकता दें, अन्यथा दाएं।rightBoundary(): नोड null या लीफ है तो लौटें; दाएं बच्चे को प्राथमिकता दें, अन्यथा बाएं; वापसी पर मान जोड़ें (ताकि क्रम सही रहे)।leaves(): नोड null है तो लौटें; यदि लीफ है तो मान जोड़ें; बाएं और दाएं पर रिकर्सिवली कॉल करें।- मुख्य विधि: ret साफ करें; यदि रूट null तो लौटाएं; रूट का मान जोड़ें; leftBoundary(रूट->बाएं); leaves(रूट->बाएं); leaves(रूट->दाएं); rightBoundary(रूट->दाएं); ret लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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> ret; void leftBoundary(TreeNode* node){ if (!node || node->val == 0 || (!node->left && !node->right)) return; ret.push_back(node->val); if (node->left && node->left->val != 0) leftBoundary(node->left); else leftBoundary(node->right); } void rightBoundary(TreeNode* node){ if (!node || node->val == 0 || (!node->left && !node->right)) return; if (node->right && node->right->val != 0) { rightBoundary(node->right); } else { rightBoundary(node->left); } ret.push_back(node->val); } void leaves(TreeNode* node){ if (!node || node->val == 0) return; if (!node->left && !node->right) { ret.push_back(node->val); } leaves(node->left); leaves(node->right); } vector<int> boundaryOfBinaryTree(TreeNode* root){ ret.clear(); if (!root) return ret; ret.push_back(root->val); leftBoundary(root->left); leaves(root->left); leaves(root->right); rightBoundary(root->right); return ret; } }; main(){ Solution ob; vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10}; TreeNode *root = make_tree(v); print_vector(ob.boundaryOfBinaryTree(root)); }
इनपुट
{1,2,3,4,5,6,NULL,NULL,NULL,7,8,9,10}
आउटपुट
[1, 2, 4, 7, 8, 9, 10, 6, 3, ]
