C++ এ গভীরতম নোডের যোগফল খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের এর গভীরতম পাতার মানের সমষ্টি খুঁজে বের করতে হবে। তাই গাছটি যদি −

এর মত হয়

তাহলে আউটপুট হবে 11।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি মানচিত্র m, এবং maxDepth
সংজ্ঞায়িত করুন
একটি পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন সমাধান(), এটি নোড এবং স্তর গ্রহণ করবে, প্রাথমিকভাবে স্তরটি 0
যদি নোড উপস্থিত না থাকে, তাহলে ফিরুন
maxDepth :=লেভেলের সর্বোচ্চ এবং maxDepth
নোডের মান দ্বারা m[স্তর] বাড়ান
সমাধান (নোডের বামে, স্তর + 1)
সমাধান (নোডের ডানদিকে, স্তর + 1)
মূল পদ্ধতিতে, maxDepth :=0 সেটআপ করুন, তারপর সমাধান করুন(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);