ในปัญหานี้ เราได้รับไบนารีทรีที่มีค่าบวกและลบ งานของเราคือ ค้นหาผลรวมระดับสูงสุดในไบนารีทรี
คำอธิบายปัญหา: เรามีไบนารีทรี เราจะหาผลรวมของทุกระดับในไบนารีทรี แล้วคืนค่าสูงสุดของมัน
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล:
ผลลัพธ์: 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