मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें इसके सबसे गहरे पत्तों के मानों का योग ढूंढना है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक मैप m और maxDepth परिभाषित करें
एक रिकर्सिव विधि solve() परिभाषित करें, यह नोड और लेवल लेगी, प्रारंभ में लेवल 0 है
यदि नोड मौजूद नहीं है, तो लौटें
maxDepth := लेवल और maxDepth का अधिकतम
m[लेवल] को नोड के मान से बढ़ाएं
solve(नोड का left, लेवल + 1)
solve(नोड का right, लेवल + 1)
मुख्य विधि में, maxDepth := 0 सेट करें, फिर solve(root, 0)
m[maxDepth] लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; 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); return m[maxDepth]; } }; main(){ TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->right = new TreeNode(6); root->right->right->right = new TreeNode(4); root->left->left->left = new TreeNode(7); Solution ob; cout << (ob.deepestLeavesSum(root)); } इनपुट
TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->right = new TreeNode(6); root->right->right->right = new TreeNode(4); root->left->left->left = new TreeNode(7);
आउटपुट
11
