Trong bài toán này, ta được cho một cây nhị phân. Nhiệm vụ: viết chương trình tìm tổng lớn nhất của các nút không phải lá (non-leaf nodes) theo từng cấp độ của cây nhị phân trong C++.
Mô tả bài toán – tính tổng tất cả nút không phải lá ở mỗi cấp độ, sau đó in tổng lớn nhất.
Hãy xem ví dụ:
Input –
Output – 9
Giải thích – tổng nút không phải lá mỗi cấp:
Cấp 1: 4 Cấp 2: 1+2 = 3 Cấp 3: 9 (4, 7 là lá) Cấp 4: 0
Để giải quyết, ta duyệt cây theo cấp độ (level order), tìm tổng các nút không phải lá (có con trái hoặc con phải), duy trì maxSum. Nếu tổng cấp độ lớn hơn maxSum, cập nhật.
Ví dụ
Chương trình minh họa triển khai giải pháp:
#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<<"Tổng lớn nhất của nút không phải lá ở một cấp của cây nhị phân là "<<maxLevelSum(root); return 0; }Kết quả
Tổng lớn nhất của nút không phải lá ở một cấp của cây nhị phân là 9