मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें उन नोड्स के मानों का योग ज्ञात करना है जिनके ग्रैंडपेरेंट का मान सम है। (एक नोड का ग्रैंडपेरेंट उसके पैरेंट का पैरेंट होता है, यदि वह मौजूद है।) यदि ऐसा कोई नोड नहीं है जिसका ग्रैंडपेरेंट सम-वैल्यू वाला हो, तो 0 लौटाएं। यदि ट्री इस प्रकार है -
तो आउटपुट 18 होगा। लाल नोड्स वे हैं जिनके ग्रैंडपेरेंट का मान सम है, जबकि नीले नोड्स सम-वैल्यू वाले ग्रैंडपेरेंट हैं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- 'parent' नामक एक मैप परिभाषित करें
- 'solve()' नामक एक मेथड परिभाषित करें, जो नोड और par लेगा
- यदि नोड null है, तो लौटें
- यदि par null नहीं है और par parent में मौजूद है और parent[par] 0 नहीं है और parent[par] का मान सम है, तो
- res := res + नोड का मान
- parent[node] := par
- solve(नोड का लेफ्ट, नोड)
- solve(नोड का राइट, नोड)
- मेन मेथड से, res := 0 सेट करें, solve(root, Null) कॉल करें, फिर res लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें -
#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; } class Solution { public: int res; map <TreeNode*, TreeNode*> parent; void solve(TreeNode* node, TreeNode* par = NULL){ if(!node)return; if(par && parent.count(par) && parent[par] && parent[par]->val % 2 == 0){ res += node->val; } parent[node] = par; solve(node->left, node); solve(node->right, node); } int sumEvenGrandparent(TreeNode* root) { res = 0; parent.clear(); solve(root); return res; } }; main(){ vector<int> v = {6,7,8,2,7,1,3,9,NULL,1,4,NULL,NULL,NULL,5}; TreeNode *root = make_tree(v); Solution ob; cout << (ob.sumEvenGrandparent(root)); }इनपुट
[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
आउटपुट
18
