ধরুন আমাদের কাছে N নোড সহ একটি বাইনারি গাছের মূল রয়েছে, এখানে গাছের প্রতিটি নোডে রয়েছে node.val কয়েন সংখ্যা, এবং মোট N কয়েন রয়েছে। এক চালে, আমরা দুটি সংলগ্ন নোড বেছে নিতে পারি এবং একটি নোড থেকে অন্য নোডে শুধুমাত্র একটি মুদ্রা সরাতে পারি। (অভিভাবক থেকে শিশু নোডে, বা শিশু থেকে পিতামাতার নোডে সরানো হতে পারে।) প্রতিটি নোডে ঠিক একটি কয়েন তৈরি করার জন্য আমাদের প্রয়োজনীয় চালের সংখ্যা খুঁজে বের করতে হবে।
তাই গাছটি যদি −
এর মত হয়তারপর আউটপুট হবে 3। বাম শিশু থেকে, রুটে 2টি কয়েন পাঠান (প্রতিটি মুদ্রার জন্য একটি চাল, তাই মোট 2টি চাল), তারপর একটি কয়েন রুট থেকে ডান শিশুর কাছে সরান, তাই মোট 3টি চাল রয়েছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সমাধান() নামে একটি পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন, এটি রুট
নামে একটি নোড নেবে -
রুট শূন্য হলে, 0
ফেরত দিন -
l :=সমাধান করুন(মূলের বামে)
-
r :=সমাধান করুন(মূলের ডানদিকে)
-
উত্তর :=|l| + |r|
-
l + r + রুটের মান – 1
ফেরত দিন -
প্রধান বিভাগে, উত্তর সেট করুন :=0, কল সল্ভ(রুট), তারপর উত্তর দিন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
int ans;
int solve(TreeNode* root){
if(!root)return 0;
int l = solve(root->left);
int r = solve(root->right);
ans += abs(l) + abs(r);
return l + r + root->val - 1;
}
int distributeCoins(TreeNode* root) {
ans = 0;
solve(root);
return ans;
}
};
main(){
vector<int> v = {0,3,0};
TreeNode *root = make_tree(v);
Solution ob;
cout << (ob.distributeCoins(root));
} ইনপুট
[0,3,0]
আউটপুট
3
