সমস্যা বিবৃতি
একটি বাইনারি ট্রি দেওয়া হয়েছে যাতে প্রতিটি নোড উপাদানে একটি সংখ্যা থাকে। কাজটি হল এক লিফ নোড থেকে অন্য লিফ নোড পর্যন্ত ন্যূনতম সম্ভাব্য যোগফল খুঁজে বের করা।
উদাহরণ
উপরের গাছে ন্যূনতম সাব পাথ হল -6 নিম্নরূপ:(-4) + 3 + 2 + (-8) + 1
অ্যালগরিদম
ধারণাটি হল পুনরাবৃত্তিমূলক কলগুলিতে দুটি মান বজায় রাখা -
- কারেন্ট নোডের নিচে রুট করা সাবট্রির জন্য ন্যূনতম রুট থেকে লিফ পাথ যোগফল
- পাতার মধ্যে ন্যূনতম পথের যোগফল
- প্রতিটি পরিদর্শন করা নোড X-এর জন্য, X-এর বাম এবং ডান উপ-বৃক্ষে আমাদের ন্যূনতম মূল থেকে পাতার যোগফল খুঁজে বের করতে হবে। তারপর X-এর ডেটার সাথে দুটি মান যোগ করুন এবং বর্তমান ন্যূনতম পথ যোগফলের সাথে যোগফলের তুলনা করুন
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int data;
struct node *left;
struct node *right;
} node;
node *newNode(int data) {
node *n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
int getMinPath(node *root, int &result) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
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);
}
if (root->left == NULL) {
return root->data + rightSum;
} else {
return root->data + leftSum;
}
}
int getMinPath(node *root) {
int result = INT_MAX;
getMinPath(root, result);
return result;
}
node *createTree() {
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);
return root;
}
int main() {
node *root = createTree();
cout << "Minimum sum path = " << getMinPath(root) << endl;
return 0;
} আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেআউটপুট
Minimum sum path = -6
