ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের দীর্ঘতম পথের দৈর্ঘ্য গণনা করতে হবে যা ক্রমবর্ধমান ক্রমে ধারাবাহিক মান সহ নোড নিয়ে গঠিত। প্রতিটি নোডকে দৈর্ঘ্য 1 এর পথ হিসাবে বিবেচনা করা হবে।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট 3 হবে কারণ (11, 12, 13) সর্বাধিক ধারাবাহিক পথ।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন সংজ্ঞায়িত করুন সমাধান(), এটি রুট, prev_data, prev_length,
- যদি রুট অ-শূন্য হয়, তাহলে −
- প্রত্যাবর্তন পূর্বের_দৈর্ঘ্য
- cur_data :=রুটের ভ্যাল
- যদি cur_data prev_data + 1 এর মত হয়, তাহলে −
- সর্বোচ্চ রিটার্ন করুন(রুটের বামে, cur_data, prev_length+1) এবং solve(root এর ডান, cur_data, prev_length+1)
- newPathLen :=সমাধানের সর্বাধিক (মূলের বামে, cur_data, 1) এবং সমাধান (রুটের ডানদিকে, cur_data, 1)
- সর্বোচ্চ prev_length এবং newPathLen ফেরত দিন
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
- যদি রুট NULL এর মত হয়, তাহলে −
- রিটার্ন 0
- রিটার্ন সলভ(root, val of root-1, 0)
উদাহরণ (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;
}
};
int solve(TreeNode *root, int prev_data, int prev_length){
if (!root)
return prev_length;
int cur_data = root->val;
if (cur_data == prev_data+1){
return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
}
int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
return max(prev_length, newPathLen);
}
int maxLen(TreeNode *root){
if (root == NULL)
return 0;
return solve(root, root->val-1, 0);
}
int main(){
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(11);
root->right = new TreeNode(9);
root->left->left = new TreeNode(13);
root->left->right = new TreeNode(12);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(8);
cout << maxLen(root);
return 0;
} ইনপুট
TreeNode *root = new TreeNode(10); root->left = new TreeNode(11); root->right = new TreeNode(9); root->left->left = new TreeNode(13); root->left->right = new TreeNode(12); root->right->left = new TreeNode(13); root->right->right = new TreeNode(8);
আউটপুট
3
