C++で最小の合計を持つツリーレベルを見つけるプログラム

二分木があり、そのルートのレベルが1、子のレベルが2などであると仮定します。レベルXのノードのすべての値の合計が最小になるように、最小のレベルXを見つける必要があります。したがって、ツリーが次のような場合-

合計が4– 10 =-6であるため、出力は2になります。これは最小です。

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

• level：=1、sum：=rの値、ansLevel：=level、ansSum：=sum

• キューqを定義し、指定されたノードrをqに挿入します

• qが空ではない間

  • 容量：=qのサイズ

  • レベルを1増やし、合計：=0

  • 容量が0ではない場合

    • node：=qからフロントノード、qからノードを削除

    • ノードの権利が有効な場合、sum：=sum +右ノードの値、rightを挿入

    • ノードをqに

    • ノードの左側が有効な場合、sum：=sum +左側のノードの値、leftnodeをqに挿入

    • 容量を1つ減らします

  • ansSum

• ansLevelを返す

理解を深めるために、次の実装を見てみましょう-

例

#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 solve(TreeNode* r) {
      int level = 1, sum = r->val;
      int ansLevel = level, ansSum = sum;
      queue <TreeNode*> q;
      q.push(r);
      while(!q.empty()){
         int capacity = q.size();
         level++;
         sum = 0;
         while(capacity--){
            TreeNode* node = q.front();
            q.pop();
            if(node->right){
               sum += node->right->val;
               q.push(node->right);
            }
            if(node->left){
               sum += node->left->val;
               q.push(node->left);
            }
         }
         if(ansSum>sum){
            ansSum = sum;
            ansLevel = level;
         }
      }
      return ansLevel;
   }
};
main(){
   TreeNode *root = new TreeNode(5);
   root->left = new TreeNode(4);
   root->right = new TreeNode(-10);
   root->left->right = new TreeNode(-2);
   root->right->left = new TreeNode(-7);
   root->right->right = new TreeNode(15);
   Solution ob;
   cout <<ob.solve(root);
}

入力

TreeNode *root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(-10);
root->left->right = new TreeNode(-2);
root->right->left = new TreeNode(-7);
root->right->right = new TreeNode(15);

出力

2