सी ++ में सबसे गहरे नोड्स का योग खोजने का कार्यक्रम

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें इसकी सबसे गहरी पत्तियों के मूल्यों का योग ज्ञात करना होगा। तो अगर पेड़ जैसा है -

तब आउटपुट 11 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

मानचित्र m, और maxDepth
. को परिभाषित करें
एक पुनरावर्ती विधि हल करें () को परिभाषित करें, यह नोड और स्तर लेगा, प्रारंभ में स्तर 0 है
यदि नोड मौजूद नहीं है, तो वापस लौटें
अधिकतम गहराई :=अधिकतम स्तर और अधिकतम गहराई
नोड के मान से m[स्तर] बढ़ाएं
हल करें (नोड के बाएं, स्तर + 1)
हल करें (नोड का अधिकार, स्तर + 1)
मुख्य विधि में, maxDepth सेटअप करें:=0, फिर हल करें (रूट, 0)
वापसी एम [अधिकतम गहराई]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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);