แนวคิด
สำหรับ Binary Tree ที่กำหนด ให้คืนค่าที่ตามมา
-
ในทุกระดับ ให้คำนวณผลรวมของใบทั้งหมดหากมีใบในระดับนี้ อย่างอื่นละเว้น
-
คำนวณการคูณผลรวมทั้งหมดแล้วส่งคืน
อินพุต
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
วิธีการ
สำหรับ Simple Solution เดียว เราจะคำนวณผลรวมลีฟซ้ำสำหรับระดับทั้งหมดโดยเริ่มจากบนลงล่าง หลังจากนั้นคูณผลรวมของระดับที่มีใบ ความซับซ้อนของเวลาของโซลูชันนี้จะเป็น 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
