ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের সেই বাইনারি ট্রিতে দীর্ঘতম ধারাবাহিক পথের দৈর্ঘ্য খুঁজে বের করতে হবে। এখানে পথ বাড়তে বা কমতে পারে। সুতরাং উদাহরণ হিসাবে [1,2,3,4] এবং [4,3,2,1] উভয়কেই একটি বৈধ পথ হিসাবে বিবেচনা করা হয়, কিন্তু পথ [1,2,4,3] একটি বৈধ নয়৷
অন্যথায়, পথটি শিশু-পিতা-মাতা-সন্তানের ক্রমানুসারে হতে পারে, যেখানে পিতামাতা-সন্তানের ক্রম আবশ্যক নয়।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে 3 কারণ দীর্ঘতম একটানা পথ হবে [1, 2, 3] বা [3, 2, 1]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন সংজ্ঞায়িত করুন solveUtil(), এটি নোড নেবে,
-
যদি নোডটি শূন্য হয়, তাহলে −
-
{ 0, 0 }
ফেরত দিন
-
-
left =solveUtil(নোডের বামে)
-
left =solveUtil(নোডের ডানদিকে)
-
এক জোড়া তাপমাত্রা সংজ্ঞায়িত করুন :={1,1}
-
যদি নোডের বাঁদিকে উপস্থিত থাকে এবং নোডের বাম দিকের মান নোড + 1-এর মানের সমান হয়, তাহলে −
-
temp.first :=সর্বাধিক temp.first এবং 1 + left.first
-
উত্তর :=সর্বাধিক উত্তর এবং temp.first
-
-
যদি নোডের ডানদিকে থাকে এবং নোডের ডানের মান নোড + 1-এর মানের সমান হয়, তাহলে −
-
temp.first :=সর্বাধিক temp.first এবং 1 + right.first
-
উত্তর :=সর্বাধিক উত্তর এবং temp.first
-
-
যদি নোডের বাম অংশ উপস্থিত থাকে এবং নোডের বাম দিকের মান নোড - 1-এর মানের সমান হয়, তাহলে −
-
temp.second :=সর্বাধিক temp.second এবং 1 + left.second
-
উত্তর :=সর্বোচ্চ উত্তর এবং temp.second
-
-
যদি নোডের ডানদিকে উপস্থিত থাকে এবং নোডের ডানের মান নোড - 1-এর মানের সমান হয়, তাহলে −
-
temp.second :=সর্বোচ্চ temp.second এবং 1 + right.second
-
উত্তর :=সর্বোচ্চ উত্তর এবং temp.second
-
-
উত্তর :=সর্বাধিক { ans এবং temp.first + temp.second - 1 }
-
রিটার্ন টেম্প
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
উত্তর :=0
-
solveUtil(root)
-
উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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;
pair<int, int> solveUtil(TreeNode* node){
if (!node) {
return { 0, 0 };
}
pair<int, int> left = solveUtil(node->left);
pair<int, int> right = solveUtil(node->right);
pair<int, int> temp = { 1, 1 };
if (node->left && node->left->val == node->val + 1) {
temp.first = max(temp.first, 1 + left.first);
ans = max(ans, temp.first);
}
if (node->right && node->right->val == node->val + 1) {
temp.first = max(temp.first, 1 + right.first);
ans = max(ans, temp.first);
}
if (node->left && node->left->val == node->val - 1) {
temp.second = max(temp.second, 1 + left.second);
ans = max(ans, temp.second);
}
if (node->right && node->right->val == node->val - 1) {
temp.second = max(temp.second, 1 + right.second);
ans = max(ans, temp.second);
}
ans = max({ ans, temp.first + temp.second - 1 });
return temp;
}
int longestConsecutive(TreeNode* root){
ans = 0;
solveUtil(root);
return ans;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
cout << (ob.longestConsecutive(root));
} ইনপুট
TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3);
আউটপুট
3
