সমস্যা বিবরণ
একটি বাইনারি ট্রি দেওয়া আছে যেখানে প্রতিটি নোডে একটি সংখ্যা রয়েছে। এক লিফ নোড থেকে অন্য লিফ নোড পর্যন্ত ন্যূনতম সম্ভাব্য যোগফল বের করতে হবে।
উদাহরণ
উপরের ট্রিতে ন্যূনতম পথ -৬: (-৪) + ৩ + ২ + (-৮) + ১
অ্যালগরিদম
রিকারসিভ কলে দুটি মান বজায় রাখা হয়:
- কারেন্ট নোডের অধীনে লিফ পর্যন্ত ন্যূনতম রুট-টু-লিফ পথ সম।
- দুটি লিফের মধ্যে ন্যূনতম পথ সম।
প্রতিটি নোড X-এর জন্য বাম ও ডান সাবট্রির ন্যূনতম রুট-টু-লিফ সম বের করে X-এর ডেটা যোগ করে এবং বর্তমান মিনিমামের সাথে তুলনা করা হয়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* newNode(int data) {
Node* n = new Node;
n->data = data; n->left = n->right = NULL;
return n;
}
int getMinPath(Node* root, int &result) {
if (!root) return 0;
if (!root->left && !root->right) return root->data;
int leftSum = getMinPath(root->left, result);
int rightSum = getMinPath(root->right, result);
if (root->left && root->right) {
result = min(result, root->data + leftSum + rightSum);
return min(root->data + leftSum, root->data + rightSum);
}
return root->data + (root->left ? leftSum : rightSum);
}
int getMinPath(Node* root) {
int result = INT_MAX;
getMinPath(root, result);
return result;
}
int main() {
Node* root = newNode(2);
root->left = newNode(3);
root->right = newNode(-8);
root->left->left = newNode(5);
root->left->right = newNode(-4);
root->right->left = newNode(1);
root->right->right = newNode(10);
cout << "Minimum sum path = " << getMinPath(root) << endl;
return 0;
}
আউটপুট
Minimum sum path = -6
