在C ++中查找相同级别的叶子数据总和的乘法
概念
对于给定的二叉树，为其返回以下值。
对于每个级别，如果此级别有叶子，则计算所有叶子的总和。否则忽略它。
计算所有总和的乘法并返回。
输入值
Root of following tree
3
/ \
8 6
\
10输出结果
80
第一层没有叶子。第二层有一个叶子8，第三层也有一个叶子10。所以结果是8*10=80
输入值
Root of following tree
3
/ \
8 6
/ \ \
9 7 10
/ \ / \
2 12 5 11输出结果
270
前两个级别没有叶子。第三级具有单叶9。最后一级具有四叶2、12、5和11。因此结果为9*（2+12+5+11）=270
方法
关于一个简单的解决方案，我们从上到下递归计算所有级别的叶子和。之后，将具有叶子的水平的总和相乘。在这里，该解决方案的时间复杂度将为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