C++ এ বাইনারি ট্রি দীর্ঘতম ধারাবাহিক ক্রম

ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের পরীক্ষা করতে হবে যে আমরা দীর্ঘতম ক্রমাগত ক্রম পথের দৈর্ঘ্য খুঁজে পাচ্ছি কিনা। যদি পথটি পিতামাতা-সন্তান সংযোগ বরাবর গাছের যেকোন নোড থেকে শুরু হওয়া কিছু নোড থেকে নোডের যেকোন ক্রম নির্দেশ করে। দীর্ঘতম ক্রমাগত পথটি পিতামাতা থেকে সন্তানকে অনুসরণ করতে হবে তবে বিপরীত নয়।

সুতরাং, যদি ইনপুট মত হয়,

তাহলে আউটপুট হবে 3, যেহেতু দীর্ঘতম ক্রমাগত সিকোয়েন্স পাথ হল 3-4-5, তাই 3 রিটার্ন করুন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন solveUtil() সংজ্ঞায়িত করুন, এটি নোড, পূর্ববর্তী, লেন 1 দিয়ে শুরু করবে,

• যদি নোড নাল হয়, তাহলে −

  • ফেরত

• যদি পূর্ববর্তী + 1 নোডের ভ্যালের মতো হয়, তাহলে −

  • (লেন 1 দ্বারা বাড়ান)

  • উত্তর :=সর্বোচ্চ উত্তর এবং লেন

  • solveUtil(নোডের বাম, নোডের ভাল, লেন)

  • solveUtil(নোডের ডান, নোডের ভাল, লেন)

• অন্যথায়

  • solveUtil(নোডের বাম, নোডের ভাল, 1)

  • solveUtil(নোডের ডান, নোডের ভাল, 1)

• একটি ফাংশন সংজ্ঞায়িত করুন সমাধান(), এটি A,

  লাগবে

• উত্তর :=1

• solveUtil(A, -infinity)

• উত্তর ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• যদি মূল শূন্য হয়, তাহলে −

  • ফেরত 0

• রিটার্ন সল্ভ(রুট)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#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;
   void solveUtil(TreeNode* node, int prev, int len = 1){
      if (!node)
         return;
      if (prev + 1 == node->val) {
         len++;
         ans = max(ans, len);
         solveUtil(node->left, node->val, len);
         solveUtil(node->right, node->val, len);
      }
      else {
         solveUtil(node->left, node->val, 1);
         solveUtil(node->right, node->val, 1);
      }
   }
   int solve(TreeNode* A){
      ans = 1;
      solveUtil(A, INT_MIN);
      return ans;
   }
   int longestConsecutive(TreeNode* root){
      if (!root)
         return 0;
      return solve(root);
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(1);
   root->right = new TreeNode(3);
   root->right->left = new TreeNode(2);
   root->right->right = new TreeNode(4);
   root->right->right->right = new TreeNode(5);
   cout << (ob.longestConsecutive(root));
}

ইনপুট

TreeNode *root = new TreeNode(1);
root->right = new TreeNode(3);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(4);
root->right->right->right = new TreeNode(5);

আউটপুট

3