ধরা যাক একটি বাইনারি ট্রির রুট দেওয়া আছে যেখানে N নোড আছে, প্রতিটি নোডে node.val সংখ্যক কয়েন রয়েছে এবং মোট N টি কয়েন আছে। একটি মুভে আমরা দুটি সংলগ্ন নোড বেছে নিতে পারি এবং একটি কয়েন এক নোড থেকে অন্য নোডে সরাতে পারি (গাঁটার থেকে শাখায় বা শাখা থেকে গাঁটার দিকে)। প্রতিটি নোডে ঠিক একটি কয়েন থাকতে হলে কতগুলো মুভ দরকার হবে তা বের করতে হবে।
যদি ট্রি নিচেরভাবে হয় −
তবে আউটপুট হবে 3। বাম শাখা থেকে রুটে ২ টি কয়েন পাঠানো হয় (প্রতিটি কয়েনের জন্য একটা মুভ, মোট ২ মুভ), তারপর রুট থেকে ডান শাখায় ১ টি কয়েন সরানো হয়, সুতরাং মোট ৩ মুভ।
এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব −
solve() নামে একটি রিকারসিভ মেথড সংজ্ঞা করব, যা রুট নোড নিবে
যদি রুট নাল হয়, তবে ০ রিটার্ন করব
l := solve(রুটের বাম শাখা)
r := solve(রুটের ডান শাখা)
ans := |l| + |r|
রিটার্ন l + r + রুটের মান - ১
মেইন সেকশনে ans := ০ সেট করে solve(রুট) কল করব, তারপর ans রিটার্ন করব
উদাহরণ
#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
