สมมติว่าเรามีไบนารีทรี ระดับของรูทคือ 1 ระดับของลูกคือ 2 เป็นต้น เราต้องหาระดับ X ที่เล็กที่สุดเพื่อให้ผลรวมของค่าทั้งหมดของโหนดที่ระดับ X มีค่าน้อยที่สุด ดังนั้นถ้าต้นไม้เป็นเหมือน −
ผลลัพธ์จะเป็น 2 เนื่องจากผลรวมคือ 4 – 10 =-6 ซึ่งเป็นค่าต่ำสุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ระดับ :=1, ผลรวม :=ค่าของ r, ansLevel :=ระดับ, ansSum :=ผลรวม
-
กำหนดคิว q แทรกโหนดที่กำหนด r ลงใน q
-
ในขณะที่ q ไม่ว่างเปล่า
-
ความจุ :=ขนาดของ q
-
เพิ่มระดับขึ้น 1 ผลรวม :=0
-
ในขณะที่ความจุไม่ใช่ 0
-
โหนด :=โหนดหน้าจาก q ลบโหนดออกจาก q
-
ถ้าด้านขวาของโหนดถูกต้อง ดังนั้น sum :=sum + ค่าของโหนดที่ถูกต้อง ให้แทรกด้านขวา
- โหนดเป็น q
-
หากโหนดด้านซ้ายถูกต้อง ดังนั้น sum :=sum + ค่าของโหนดด้านซ้าย ให้แทรกโหนดด้านซ้ายลงใน q
-
ลดความจุลง 1
-
-
ถ้า ansSum
-
-
กลับ ansLevel
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น−
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
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;
}
};
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
