C++-এ Binary Tree Longest Consecutive Sequence: বাইনারি ট্রিতে সর্বোচ্চ সতত ক্রম খুঁজে বের করা

একটি বাইনারি ট্রি দেওয়া আছে। পেরেন্ট থেকে চাইল্ড ডিরেকশনে (রিভার্স নয়) সর্বোচ্চ দৈর্ঘ্যের কনsekutিভ সিকোয়েন্স (consecutive sequence) পাথ খুঁজে বের করতে হবে। পাথ মানে কোনো নোড থেকে শুরু করে পেরেন্ট-চাইল্ড কানেকশন ফলো করে যেকোনো নোড পর্যন্ত।

উদাহরণ

আউটপুট: 3 (পাথ: 3-4-5, দৈর্ঘ্য ৩)।

সমাধানের পদ্ধতি (DFS + Length Tracking)

গ্লোবাল ভেরিয়েবল ans (সর্বোচ্চ দৈর্ঘ্য)।
রিকারসিভ ফাংশন solveUtil(node, prev, len):
- prev = পেরেন্ট নোডের ভ্যালু, len = বর্তমান কনsekutিভ দৈর্ঘ্য (ডিফল্ট ১)।
- যদি নোড নাল হয়, তবে রিটার্ন।
- যদি prev + 1 == node->val (কনsekutিভ), তবে:
  - len++, ans = max(ans, len)।
  - বাম ও ডান চাইল্ডের জন্য solveUtil(child, node->val, len) কল করুন।
- অন্যথায় (কনsekutিভ ভাঙল):
  - বাম ও ডান চাইল্ডের জন্য নতুন সিকোয়েন্স শুরু করুন: solveUtil(child, node->val, 1)।
মেইন ফাংশন solve(root): ans=1, solveUtil(root, INT_MIN), ans রিটার্ন।
রুট নাল হলে ০ রিটার্ন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = 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);