मान लीजिए हमारे पास एक बाइनरी ट्री है, हमारे पास मान v और गहराई d भी है, हमें दिए गए गहराई d पर मान v वाले नोड्स की एक पंक्ति जोड़नी है। रूट नोड गहराई 1 पर है। हमें इस ऑपरेशन को करने के लिए निम्न नियम का पालन करना होगा:
चूंकि हमें गहराई d पता है, गहराई d-1 पर प्रत्येक वैध ट्री नोड N के लिए, हमें मान v वाले दो ट्री नोड्स बनाने होंगे जो N के बाएं उपट्री रूट और दाएं उपट्री रूट हों। और N का मूल बायां उपट्री नए बाएं उपट्री रूट का बायां उपट्री होगा, इसका मूल दायां उपट्री नए दाएं उपट्री रूट का दायां उपट्री होगा। जब गहराई d 1 है, इसका मतलब है कि गहराई d-1 बिल्कुल नहीं है, फिर मान v वाला एक ट्री नोड पूरे मूल ट्री के नए रूट के रूप में बनाएं, और मूल ट्री नए रूट का बायां उपट्री होगा।
हल करने की विधि
हम निम्न चरणों का पालन करेंगे:
- यदि d == 1, तो मान v वाला नया नोड बनाएं, उसका बायां बच्चा रूट बनाएं, और रूट को नए नोड पर सेट करें।
- अन्यथा:
- (नोड, स्तर) युग्म का एक स्टैक st परिभाषित करें।
- {root, 2} को st में डालें।
- जब तक st खाली न हो:
- शीर्ष तत्व निकालें, स्तर और नोड प्राप्त करें।
- यदि स्तर == d, तो मान v वाले दो नए नोड्स बनाएं, नोड के बाएं और दाएं बच्चों को नए नोड्स के बाएं और दाएं बच्चों के रूप में संलग्न करें, और नोड के बाएं और दाएं बच्चों को नए नोड्स पर सेट करें।
- अन्यथा, यदि बायां/दायां बच्चा वैध है, तो उन्हें स्तर+1 के साथ st में डालें।
- रूट लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; 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; } void tree_level_trav(TreeNode*root){ if (root == NULL) return; cout << "["; queue<TreeNode *> q; TreeNode *curr; q.push(root); q.push(NULL); while (q.size() > 1) { curr = q.front(); q.pop(); if (curr == NULL){ q.push(NULL); } else { if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); if(curr == NULL || curr->val == 0){ cout << "null" << ", "; } else{ cout << curr->val << ", "; } } } cout << "]"<<endl; } class Solution { public: TreeNode* addOneRow(TreeNode* root, int v, int d) { if (d == 1) { TreeNode* temp = new TreeNode(v); temp->left = root; root = temp; } else { stack<pair<TreeNode*, int> > st; st.push({ root, 2 }); int lvl = 0; pair<TreeNode*, int> temp; TreeNode* node; while (!st.empty()) { temp = st.top(); st.pop(); lvl = temp.second; node = temp.first; if (lvl == d) { TreeNode* temp1 = new TreeNode(v); TreeNode* temp2 = new TreeNode(v); temp1->left = node->left; temp2->right = node->right; node->left = temp1; node->right = temp2; } else { if (node->left && node->left->val != 0) { st.push({ node->left, lvl + 1 }); } if (node->right && node->right->val != 0) { st.push({ node->right, lvl + 1 }); } } } } return root; } }; main(){ Solution ob; vector<int> v = {4,2,6,3,1,5}; TreeNode *root = make_tree(v); tree_level_trav(ob.addOneRow(root, 1, 2)); }
इनपुट
{4,2,6,3,1,5}, 1, 2
आउटपुट
[4, 1, 1, 2, 6, 3, 1, 5, ]
