C++で同じレベルの葉のデータの合計の乗算を見つけます

コンセプト

与えられた二分木に関して、次の値を返します。

• すべてのレベルに関して、このレベルに葉がある場合は、すべての葉の合計を計算します。それ以外の場合は無視してください。

• すべての合計の乗算を計算して返します。

入力

Root of following tree
      3
     / \
    8   6
         \
          10

出力

80

最初のレベルには葉がありません。 2番目のレベルには1つのリーフ8があり、3番目のレベルにも1つのリーフ10があります。したがって、結果は8 * 10 =80

入力

Root of following tree
             3
           /  \
           8   6
          / \   \
         9 7   10
           / \  / \
           2 12 5 11

出力

270

最初の2つのレベルには葉がありません。 3番目のレベルには単一のリーフ9があります。最後のレベルには4つのリーフ2、12、5、および11があります。したがって、結果は9 *（2 + 12 + 5 + 11）=270

メソッド

1つの単純なソリューションに関して、上から下に向かってすべてのレベルのリーフの合計を再帰的に計算します。その後、葉のあるレベルの合計を掛けます。ここで、このソリューションの時間計算量はO（n ^ 2）になります。

ここでも、効率的なソリューションに関して、キューベースのレベル順序トラバーサルを実装します。ここでは、トラバーサルを実行しながら、すべての異なるレベルを個別に処理します。処理されたすべてのレベルについて、葉があるかどうかを確認します。この場合、リーフノードの合計を計算している場合。最後に、すべての合計の積を返します。

例

/* Iterative C++ program to find sum of data of all leaves
of a binary tree on same level and then multiply sums
obtained of all levels. */
#include <bits/stdc++.h>
using namespace std;
// Shows a Binary Tree Node
struct Node1 {
   int data1;
   struct Node1 *left1, *right1;
};
// Shows helper function to check if a Node is leaf of tree
bool isLeaf(Node1* root1){
   return (!root1->left1 && !root1->right1);
}
/* Compute sum of all leaf Nodes at each level and returns
multiplication of sums */
int sumAndMultiplyLevelData(Node1* root1){
   // Here tree is empty
   if (!root1)
      return 0;
   int mul1 = 1; /* Used To store result */
   // Build an empty queue for level order tarversal
   queue<Node1*> q1;
   // Used to Enqueue Root and initialize height
   q1.push(root1);
   // Perform level order traversal of tree
   while (1) {
      // NodeCount1 (queue size) indicates number of Nodes
      // at current lelvel.
      int NodeCount1 = q1.size();
      // Now if there are no Nodes at current level, we are done
      if (NodeCount1 == 0)
         break;
      // Used to initialize leaf sum for current level
         int levelSum1 = 0;
      // Shows a boolean variable to indicate if found a leaf
      // Node at current level or not
      bool leafFound1 = false;
      // Used to Dequeue all Nodes of current level and Enqueue
      all
      // Nodes of next level
      while (NodeCount1 > 0) {
         // Process next Node of current level
         Node1* Node1 = q1.front();
         /* Now if Node is a leaf, update sum at the level */
         if (isLeaf(Node1)) {
            leafFound1 = true;
            levelSum1 += Node1->data1;
         }
         q1.pop();
         // Add children of Node
         if (Node1->left1 != NULL)
            q1.push(Node1->left1);
         if (Node1->right1 != NULL)
            q1.push(Node1->right1);
         NodeCount1--;
      }
      // Now if we found at least one leaf, we multiply
      // result with level sum.
      if (leafFound1)
         mul1 *= levelSum1;
   }
   return mul1; // Here, return result
}
//Shows utility function to create a new tree Node
Node1* newNode(int data1){
   Node1* temp1 = new Node1;
   temp1->data1 = data1;
   temp1->left1 = temp1->right1 = NULL;
   return temp1;
}
// Driver program to test above functions
int main(){
   Node1* root1 = newNode(3);
   root1->left1 = newNode(8);
   root1->right1 = newNode(6);
   root1->left1->right1 = newNode(7);
   root1->left1->left1 = newNode(9);
   root1->left1->right1->left1 = newNode(2);
   root1->left1->right1->right1 = newNode(12);
   root1->right1->right1 = newNode(10);
   root1->right1->right1->left1 = newNode(5);
   root1->right1->right1->right1 = newNode(11);
   cout << "Final product value = "
   << sumAndMultiplyLevelData(root1) <<endl;
   return 0;
}

出力

Final product value = 270