मान लीजिए हमारे पास N नोड्स वाला एक बाइनरी ट्री का रूट है, जहाँ प्रत्येक नोड में node.val संख्या में सिक्के हैं, और कुल N सिक्के हैं। एक चाल में, हम दो आसन्न नोड्स चुन सकते हैं और एक सिक्के को एक नोड से दूसरे नोड में ले जा सकते हैं (चाल पैरेंट से चाइल्ड या चाइल्ड से पैरेंट हो सकती है)। हमें वह चालों की संख्या ढूंढनी है जिससे हर नोड में ठीक एक सिक्का हो जाए।
उदाहरण: ट्री [0,3,0] (रूट=0, बायाँ=3, दायाँ=0) के लिए आउटपुट 3 होगा। बाएँ चाइल्ड से रूट में 2 सिक्के भेजें (2 चालें), फिर रूट से दाएँ चाइल्ड में 1 सिक्का भेजें (1 चाल)। कुल 3 चालें।
पोस्ट-ऑर्डर ट्रैवर्सल समाधान
- एक रिकर्सिव मेथड
solve()परिभाषित करें जो एक नोडrootलेता है। - यदि
rootnull है, तो 0 लौटाएँ। l := solve(root->left),r := solve(root->right)।ans += |l| + |r|(ग्लोबल उत्तर में निरपेक्ष मान जोड़ें)।return l + r + root->val - 1लौटाएँ (यह नोड का अतिरिक्त/घाटा सिक्के दर्शाता है)।- मुख्य फंक्शन में
ans := 0सेट करें,solve(root)कॉल करें, फिरansलौटाएँ।
C++ कार्यान्वयन
#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 ans = 0;
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;
}
};
// ट्री बनाने के लिए हेल्पर फंक्शन (लेवल ऑर्डर इनपुट से)
TreeNode* make_tree(vector<int> v) {
if (v.empty()) return NULL;
TreeNode* root = new TreeNode(v[0]);
queue<TreeNode*> q;
q.push(root);
int i = 1;
while (!q.empty() && i < v.size()) {
TreeNode* curr = q.front(); q.pop();
if (i < v.size() && v[i] != -1) {
curr->left = new TreeNode(v[i]);
q.push(curr->left);
}
i++;
if (i < v.size() && v[i] != -1) {
curr->right = new TreeNode(v[i]);
q.push(curr->right);
}
i++;
}
return root;
}
int main() {
vector<int> v = {0,3,0};
TreeNode* root = make_tree(v);
Solution ob;
cout << ob.distributeCoins(root); // आउटपुट: 3
return 0;
}
इनपुट
[0,3,0]
आउटपुट
3