สมมติว่าเรามีต้นไม้ไบนารี ระดับของรูทคือ 1 ระดับของลูกคือ 2 และเพิ่มขึ้นไปเรื่อยๆ เราต้องหาระดับ X ที่เล็กที่สุดที่ทำให้ผลรวมของค่าโหนดทั้งหมดในระดับ X นั้นน้อยที่สุด
เช่น ต้นไม้ที่มีโครงสร้างดังภาพ ผลลัพธ์จะเป็น 2 เนื่องจากผลรวมระดับ 2 คือ 4 + (-10) = -6 ซึ่งน้อยที่สุด
ขั้นตอนการแก้ปัญหา
- เริ่มต้น level = 1, sum = ค่าของรูท, ansLevel = level, ansSum = sum
- ใช้คิว (queue) สำหรับ BFS ใส่รูทเข้าไป
- วนลูปจนคิวว่าง:
- capacity = ขนาดคิว (จำนวนโหนดในระดับปัจจุบัน)
- เพิ่ม level, ตั้ง sum = 0
- วนลูป capacity ครั้ง:
- นำโหนดหน้าคิวออก (pop)
- ถ้ามีลูกขวา: บวกค่าลูกขวาเข้า sum, ใส่ลูกขวาเข้าคิว
- ถ้ามีลูกซ้าย: บวกค่าลูกซ้ายเข้า sum, ใส่ลูกซ้ายเข้าคิว
- ถ้า sum < ansSum: อัปเดต ansSum และ ansLevel
- คืนค่า ansLevel
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = right = NULL;
}
};
class Solution {
public:
int solve(TreeNode* r) {
int level = 1, sum = r->val;
int ansLevel = level, ansSum = sum;
queue<TreeNode*> q;
q.push(r);
while (!q.empty()) {
int capacity = q.size();
level++;
sum = 0;
while (capacity--) {
TreeNode* node = q.front();
q.pop();
if (node->right) {
sum += node->right->val;
q.push(node->right);
}
if (node->left) {
sum += node->left->val;
q.push(node->left);
}
}
if (ansSum > sum) {
ansSum = sum;
ansLevel = level;
}
}
return ansLevel;
}
};
int main() {
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(-10);
root->left->right = new TreeNode(-2);
root->right->left = new TreeNode(-7);
root->right->right = new TreeNode(15);
Solution ob;
cout << ob.solve(root);
}
อินพุต
TreeNode *root = new TreeNode(5); root->left = new TreeNode(4); root->right = new TreeNode(-10); root->left->right = new TreeNode(-2); root->right->left = new TreeNode(-7); root->right->right = new TreeNode(15);
เอาต์พุต
2
