C++で最も深いノードの合計を見つけるプログラム

二分木があるとしましょう。その最も深い葉の値の合計を見つける必要があります。したがって、ツリーが次のような場合-

その場合、出力は11になります。

これを解決するには、次の手順に従います-

• マップmとmaxDepthを定義します

• 再帰メソッドsolve（）を定義します。これはノードとレベルを取り、最初はレベルは0です

• ノードが存在しない場合は、戻ります

• maxDepth：=レベルの最大値とmaxDepth

• ノードの値だけm[レベル]を増やします

• 解決（ノードの左側、レベル+ 1）

• 解決（ノードの右側、レベル+ 1）

• mainメソッドで、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