C++ में बाइनरी ट्री सबसे लंबे समय तक लगातार अनुक्रम

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें यह जांचना होगा कि क्या हम सबसे लंबे क्रमागत अनुक्रम पथ की लंबाई ज्ञात कर सकते हैं। यदि पथ माता-पिता-बच्चे कनेक्शन के साथ पेड़ में किसी भी नोड से कुछ शुरुआती नोड से नोड्स के किसी अनुक्रम को संदर्भित करता है। माता-पिता से बच्चे तक लगातार सबसे लंबे रास्ते की जरूरत है, लेकिन उल्टा नहीं।

तो, अगर इनपुट पसंद है,

तो आउटपुट 3 होगा, क्योंकि सबसे लंबा क्रमागत अनुक्रम पथ 3-4-5 है, इसलिए वापसी 3.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को हल करें परिभाषित करें (), यह नोड लेगा, पिछला, लेन इसे 1 के साथ प्रारंभ करेगा,

• यदि नोड शून्य है, तो -

  • वापसी

• यदि पिछला + 1 नोड के मान के समान है, तो -

  • (लेन को 1 से बढ़ाएं)

  • उत्तर :=अधिकतम उत्तर और लेन

  • SolveUtil(नोड के बाएँ, नोड का मान, लेन)

  • SolveUtil(नोड का दायां, नोड का वैल, लेन)

• अन्यथा

  • हल करें (नोड के बाएं, नोड का वैल, 1)

  • SolveUtil(नोड का दायां, नोड का मान, 1)

• एक फ़ंक्शन हल करें () को परिभाषित करें, इसमें A,

  . लगेगा

• उत्तर :=1

• हल यूटिल (ए, -इनफिनिटी)

• वापसी उत्तर

• मुख्य विधि से निम्न कार्य करें -

• यदि रूट शून्य है, तो -

  • वापसी 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