컨셉
주어진 바이너리 트리에 대해 다음 값을 반환합니다.
-
모든 레벨에 대해 이 레벨에 리프가 있는 경우 모든 리프의 합계를 계산합니다. 그렇지 않으면 무시하십시오.
-
모든 합계의 곱을 계산하여 반환합니다.
입력
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)가 됩니다.
다시 Efficient Solution과 관련하여 우리는 Queue 기반 레벨 순서 순회를 구현합니다. 여기에서 순회를 하는 동안 우리는 모든 다른 레벨을 개별적으로 처리합니다. 처리된 모든 레벨에 대해 잎이 있는지 확인합니다. 이 경우 리프 노드의 합을 계산합니다. 마지막으로 모든 금액의 곱을 반환합니다.
예
/* 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