ในปัญหานี้ เราได้รับไบนารีทรีที่มีค่าบวกและลบ งานของเราคือ ค้นหาผลรวมระดับสูงสุดในไบนารีทรี
คำอธิบายปัญหา: เรามีไบนารีทรี เราจะหาผลรวมของทุกระดับในไบนารีทรี แล้วคืนค่าสูงสุดของมัน
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล:
ผลลัพธ์: 5
คำอธิบาย:
ผลรวมขององค์ประกอบที่ระดับ 1:3
ผลรวมขององค์ประกอบที่ระดับ 2:-3 + 4 =1
ผลรวมขององค์ประกอบที่ระดับ 3:5 - 1 + 6 - 5 =5
แนวทางการแก้ปัญหา
เพื่อแก้ปัญหา เราจำเป็นต้องสำรวจต้นไม้โดยใช้ระดับการข้ามผ่าน และสำหรับแต่ละระดับ เราจะหาผลรวมแล้วหาผลรวมระดับสูงสุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int findMaxLevelSum(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();
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;
}
int main(){
struct Node* root = newNode(3);
root->left = newNode(-3);
root->right = newNode(4);
root->left->left = newNode(5);
root->left->right = newNode(-1);
root->right->left = newNode(6);
root->right->right = newNode(-5);
cout<<"The sum of level with maximum level sum is "<<findMaxLevelSum(root);
return 0;
} ผลลัพธ์
The sum of level with maximum level sum is 5
