বাইনারি ট্রির বাউন্ডারি ট্রাভার্সাল C++-এ

সমস্যা বিবরণ

একটি বাইনারি ট্রির বাউন্ডারি নোডগুলো এন্টি-ক্লকওয়াইজ ডিরেকশনে (রুট থেকে শুরু করে) রিটার্ন করুন। বাউন্ডারি অন্তর্ভুক্ত করে: লেফট বাউন্ডারি, লিফ নোডস, রাইট বাউন্ডারি (রিভার্স অর্ডারে)। ডুপ্লিকেট নোড এড়াতে হবে।

উদাহরণ

ইনপুট: [1,2,3,4,5,6,null,null,null,7,8,9,10]

আউটপুট: [1,2,4,7,8,9,10,6,3]

অ্যালগরিদম: তিনটি ফেজে ট্রাভার্সাল

1. লেফট বাউন্ডারি: রুট থেকে লেফট-মোস্ট নোড পর্যন্ত (লিফ বাদে)। বাম চাইল্ড থাকলে বামে, নাইলে ডানে।
2. লিফ নোডস: ইন-অর্ডার বা প্রি-অর্ডার ট্রাভার্সাল দিয়ে সব লিফ কালেক্ট করুন।
3. রাইট বাউন্ডারি: রুট থেকে রাইট-মোস্ট নোড পর্যন্ত (লিফ বাদে), রিভার্স অর্ডারে আউটপুটে যোগ করুন। ডান চাইল্ড থাকলে ডানে, নাইলে বামে।

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:
    vector<int> boundary;

    void leftBoundary(TreeNode* node) {
        if (!node || (!node->left && !node->right)) return;
        boundary.push_back(node->val);
        if (node->left) leftBoundary(node->left);
        else leftBoundary(node->right);
    }

    void leaves(TreeNode* node) {
        if (!node) return;
        if (!node->left && !node->right) {
            boundary.push_back(node->val);
            return;
        }
        leaves(node->left);
        leaves(node->right);
    }

    void rightBoundary(TreeNode* node) {
        if (!node || (!node->left && !node->right)) return;
        if (node->right) rightBoundary(node->right);
        else rightBoundary(node->left);
        boundary.push_back(node->val); // রিভার্স অর্ডার
    }

    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        boundary.clear();
        if (!root) return boundary;
        boundary.push_back(root->val);
        leftBoundary(root->left);
        leaves(root->left);
        leaves(root->right);
        rightBoundary(root->right);
        return boundary;
    }
};

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

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

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

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