C++ में बाइनरी ट्री लॉन्गेस्ट कंसिक्यूटिव सीक्वेंस - माता-पिता से बच्चा पथ

समस्या विवरण

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

उदाहरण के लिए, यदि इनपुट इस तरह का ट्री है:

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

समाधान दृष्टिकोण

DFS का उपयोग करके लगातार अनुक्रम ट्रैक करें:

1. solveUtil() फ़ंक्शन परिभाषित करें जो नोड, prev, len (डिफ़ॉल्ट 1) लेता है:
   • यदि नोड null है, तो लौटें
   • यदि prev + 1 == नोड का मान:
     • len बढ़ाएं
     • ans = max(ans, len) अपडेट करें
     • बाएं और दाएं बच्चे के लिए पुनरावर्ती कॉल करें नोड के मान के साथ
   • अन्यथा:
     • बाएं और दाएं बच्चे के लिए पुनरावर्ती कॉल करें len=1 के साथ
2. solve() फ़ंक्शन परिभाषित करें जो A लेता है:
   • ans := 1
   • solveUtil(A, -अनंत) कॉल करें
   • ans लौटाएं
3. मुख्य विधि से: यदि रूट null है तो 0 लौटाएं, अन्यथा solve(रूट) लौटाएं

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; 
    } 
}; 

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); 
    } 
}; 

int 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)); 
    return 0;
}

इनपुट

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