ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือสร้างโปรแกรมที่จะค้นหาผลรวมสูงสุดของโหนดที่ไม่ใช่ใบไม้ในทุกระดับของไบนารีทรีที่กำหนดใน c++
คำอธิบายปัญหา − เราจะคำนวณผลรวมของโหนดที่ไม่ใช่ใบไม้ทั้งหมดของต้นไม้และทุกระดับ จากนั้นพิมพ์ผลรวมสูงสุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล −
ผลผลิต − 9
คำอธิบาย − ผลรวมของโหนดที่ไม่ใช่ใบในแต่ละระดับ −
Level 1: 4 Level 2: 1+2 = 3 Level 3: 9 (4, 7 are leaf nodes) Level 4: 0
เพื่อแก้ปัญหานี้ เราจะต้องทำการสำรวจระดับของไบนารีทรีและหาผลรวมของโหนดทั้งหมดที่ไม่ใช่โหนดลีฟ แล้วหาผลรวมสูงสุดของโหนดเหล่านี้
ดังนั้นในแต่ละระดับ เราจะตรวจสอบว่าโหนดมีลูกด้านซ้ายหรือขวาหรือไม่ ถ้าไม่ใช่ ให้เพิ่มลงในผลรวม และรักษา maxSum ที่จัดเก็บผลรวมสูงสุดจนถึงระดับ หากผลรวมของโหนดที่ไม่ใช่โหนดลีฟทั้งหมดมากกว่า maxSum เราจะเริ่มต้นผลรวมของระดับนั้นจนถึงค่าสูงสุด
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
int maxLevelSum(struct Node* root){
if (root == NULL)
return 0;
int maxSum = root->data;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
int levelSum = 0;
while (count--) {
Node* temp = q.front();
q.pop();
if (temp->left != NULL || temp->right != NULL)
levelSum = levelSum + temp->data;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
maxSum = max(levelSum, maxSum);
}
return maxSum;
}
struct Node* insertNode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int main() {
struct Node* root = insertNode(6);
root->left = insertNode(1);
root->right = insertNode(2);
root->left->left = insertNode(4);
root->left->right = insertNode(7);
root->right->right = insertNode(9);
root->right->right->left = insertNode(5);
cout<<"The maximum sum of all non-lead nodes at a level of the binary tree is "<<maxLevelSum(root);
return 0;
} ผลลัพธ์
The maximum sum of all non-lead nodes at a level of the binary tree is 9
