मान लीजिए कि हमारे पास एन नोड्स के साथ एक बाइनरी ट्री की जड़ है, यहां पेड़ के प्रत्येक नोड में सिक्कों की संख्या है, और कुल एन सिक्के हैं। एक चाल में, हम दो आसन्न नोड्स चुन सकते हैं और केवल एक सिक्के को एक नोड से दूसरे नोड में स्थानांतरित कर सकते हैं। (चाल माता-पिता से बाल नोड तक, या बच्चे से माता-पिता नोड तक हो सकता है।) हमें प्रत्येक नोड में एक सिक्का बनाने के लिए आवश्यक चालों की संख्या ज्ञात करनी होगी।
तो अगर पेड़ जैसा है -
फिर आउटपुट 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