বাইনারি ট্রিতে রুট-টু-লিফ পাথ ভ্যালিড সিকোয়েন্স কিনা চেক করা C++-এ

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া আছে যেখানে রুট থেকে যেকোনো লিফ পর্যন্ত পাথ একটি ভ্যালিড সিকোয়েন্স তৈরি করে। একটি ইন্টিজার অ্যারে arr দেওয়া আছে। এটি ট্রিতে কোনো রুট-টু-লিফ পাথের সাথে মিলে কিনা তা চেক করতে হবে।

উদাহরণ

ট্রি:

arr = [0,1,0,1] → আউটপুট: true (পাথ: 0→1→0→1)

অ্যালগরিদম: রিকার্সিভ DFS

রুট থেকে শুরু করে idx = ০ দিয়ে রিকার্সন।
বেস কেস:
- নোড নাল হলে → false।
- idx >= arr.size() হলে → false।
- নোড ভ্যালু != arr[idx] হলে → false।
যদি নোড লিফ হয় (চাইল্ড নেই), তবে idx == arr.size()-1 হলে true রিটার্ন করুন।
অন্যথায় বাম ও ডান চাইল্ডে idx+1 দিয়ে রিকার্সন করুন। যেকোনো একটি true দিলে true।

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:
    bool solve(TreeNode* node, vector<int>& v, int idx = 0) {
        if (!node) return false;
        if (idx >= v.size()) return false;
        if (node->val != v[idx]) return false;
        if (!node->left && !node->right) {
            return idx == v.size() - 1;
        }
        return solve(node->left, v, idx + 1) || solve(node->right, v, idx + 1);
    }

    bool isValidSequence(TreeNode* root, vector<int>& arr) {
        return solve(root, arr);
    }
};

int main() {
    // ট্রি বানান এবং টেস্ট করুন
    return 0;
}

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

ইনপুট	আউটপুট
`arr = [0,1,0,1]`	`1` (true)

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

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