মনে করুন একটি বাইনারি ট্রি আছে, আমাদের এর গভীরতম লিফ নোডগুলোর মানগুলোর যোগফল বের করতে হবে। যদি ট্রি নিচের মোতাবিক হয় -
তবে আউটপুট হবে ১৫।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- একটি ম্যাপ `m`, এবং `maxDepth` সংজ্ঞায়িত করুন
- `solve()` নামক একটি রিকার্সিভ মেথড সংজ্ঞায়িত করুন, এটি `node` এবং `level` নেবে, প্রাথমিকভাবে `level` 0
- যদি `node` না থাকে, তবে রিটার্ন করুন
- `maxDepth := max(level, maxDepth)`
- `m[level]`-কে `node`-এর মান দিয়ে বাড়ান
- `solve(node`-এর বাম, `level + 1`)
- `solve(node`-এর ডান, `level + 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
