मान लीजिए हमारे पास एक बाइनरी ट्री है, हमें इसकी सबसे गहरी पत्तियों के मानों का योग ज्ञात करना है। यदि ट्री इस प्रकार है -
तो आउटपुट 15 होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- एक मैप m और maxDepth परिभाषित करें
- एक रिकर्सिव मेथड solve() परिभाषित करें, जो नोड और लेवल लेगा, प्रारंभ में लेवल 0 है
- यदि नोड मौजूद नहीं है, तो लौटें
- maxDepth := लेवल और maxDepth का मैक्स
- m[लेवल] को नोड के मान से बढ़ाएं
- solve(नोड का लेफ्ट, लेवल + 1)
- solve(नोड का राइट, लेवल + 1)
- मेन मेथड में, maxDepth := 0 सेटअप करें, फिर solve(root, 0)
- m[maxDepth] लौटाएं
उदाहरण (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 maxDepth; map <int, int> m; void solve(TreeNode* node, int level = 0){ if(!node)return; maxDepth = max(level, maxDepth); m[level] += node->val; solve(node->left, level + 1); solve(node->right, level + 1); } int deepestLeavesSum(TreeNode* root) { maxDepth = 0; m.clear(); solve(root); //cout << maxDepth << endl; return m[maxDepth]; } }; main(){ vector<int> v = {1,2,3,4,5,NULL,6,7,NULL,NULL,NULL,NULL,8}; TreeNode *root = make_tree(v); Solution ob; cout << (ob.deepestLeavesSum(root)); }इनपुट
[1,2,3,4,5,null,6,7,null,null,null,null,8]
आउटपुट
15
