Khái niệm
Đối với Cây nhị phân đã cho, hãy trả về giá trị sau cho nó.
-
Đối với mọi cấp độ, hãy tính tổng của tất cả các lá nếu có các lá ở cấp độ này. Khác thì bỏ qua.
-
Tính nhân tất cả các tổng và trả về.
Đầu vào
Root of following tree 3 / \ 8 6 \ 10
Đầu ra
80
Cấp độ đầu tiên không có lá. Cấp thứ hai có một lá 8 và cấp ba cũng có một lá 10. Vậy kết quả là 8 * 10 =80
Đầu vào
Root of following tree 3 / \ 8 6 / \ \ 9 7 10 / \ / \ 2 12 5 11
Đầu ra
270
Hai cấp độ đầu tiên không có lá. Cấp ba có lá đơn 9. Cấp cuối có bốn lá 2, 12, 5 và 11. Vậy kết quả là 9 * (2 + 12 + 5 + 11) =270
Phương pháp
Đối với một Giải pháp Đơn giản, chúng tôi tính toán đệ quy tổng lá cho tất cả các cấp bắt đầu từ trên xuống dưới. Sau đó nhân tổng các cấp có lá. Ở đây, độ phức tạp về thời gian của giải pháp này sẽ là O (n ^ 2).
Một lần nữa Đối với Giải pháp hiệu quả, chúng tôi triển khai duyệt thứ tự ở cấp độ Hàng đợi. Ở đây, trong khi thực hiện truyền tải, chúng tôi xử lý riêng biệt tất cả các cấp độ khác nhau. Trong trường hợp này, nếu nó có thì tính tổng các nút lá. Cuối cùng, hãy trả lại sản phẩm của tất cả các khoản tiền.
Ví dụ
/* 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;
} Đầu ra
Final product value = 270