বাইনারি ট্রিতে সর্বদীর্ঘ কনsekutিভ সিকোয়েন্স II C++-এ

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া আছে। সবচেয়ে লম্বা কনsekutিভ পাথের দৈর্ঘ্য বের করতে হবে। পাথ বা ক্রমবর্ধমান (১,২,৩...) বা ক্রমঅবর্ধমান (৩,২,১...) হতে পারে। পাথ চাইল্ড-প্যারেন্ট-চাইল্ড দিকেও হতে পারে (সिर्फ প্যারেন্ট-চাইল্ড নয়)।

উদাহরণ

ট্রি:

  2
 / \
1   3

অ্যালগরিদম: পোস্ট-অর্ডার DFS

প্রতিটি নোডের জন্য দুটি ভ্যালু রিটার্ন করুন:

• inc = নোড থেকে নিচে যাওয়া ক্রমবর্ধমান পথের দৈর্ঘ্য।
• dec = নোড থেকে নিচে যাওয়া ক্রমঅবর্ধমান পথের দৈর্ঘ্য।

লোকাল আন্সার আপডেট: inc + dec - 1 (নোডটা দুবার কাউন্ট হয়েছে)।
গ্লোবাল আন্সার = সব নোডের লোকাল আন্সারের ম্যাক্স।

C++ বাস্তবায়ন

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) : val(data), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int ans = 0;

    pair<int,int> dfs(TreeNode* node) {
        if (!node) return {0,0};
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        pair<int,int> cur = {1,1}; // inc, dec

        if (node->left) {
            if (node->left->val == node->val + 1)
                cur.first = max(cur.first, 1 + left.first);
            if (node->left->val == node->val - 1)
                cur.second = max(cur.second, 1 + left.second);
        }
        if (node->right) {
            if (node->right->val == node->val + 1)
                cur.first = max(cur.first, 1 + right.first);
            if (node->right->val == node->val - 1)
                cur.second = max(cur.second, 1 + right.second);
        }
        ans = max({ans, cur.first, cur.second, cur.first + cur.second - 1});
        return cur;
    }

    int longestConsecutive(TreeNode* root) {
        ans = 0;
        dfs(root);
        return ans;
    }
};

int main() {
    Solution ob;
    TreeNode* root = new TreeNode(2);
    root->left = new TreeNode(1);
    root->right = new TreeNode(3);
    cout << ob.longestConsecutive(root); // 3
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N) — N = নোড সংখ্যা।
• স্থান জটিলতা: O(H) — রিকার্সন স্ট্যাক, H = হাইট।