C++-এ বাইনারি ট্রির ডান দিক থেকে দৃশ্য (Binary Tree Right Side View)

একটি বাইনারি ট্রি দেওয়া আছে। ট্রিকে ডান পাশ থেকে দেখা গেলে কোন নোডগুলো দেখা যাবে তা বের করতে হবে।

উদাহরণ

ট্রি:

ডান দিক থেকে দৃশ্য: [1, 3, 4]

DFS সমাধান

ডান সাবট্রি আগে ট্রাভার্স করুন, তারপর বাম সাবট্রি। প্রতিটি লেভেলের প্রথম নোডই ডান দিক থেকে দেখা যাবে।

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:
    void dfs(TreeNode* node, vector<int>& ans, int level = 0) {
        if (!node) return;
        if (level == ans.size()) ans.push_back(node->val);
        dfs(node->right, ans, level + 1);
        dfs(node->left, ans, level + 1);
    }
    
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }
};

int main() {
    vector<int> v = {1, 2, 3, NULL, 5, NULL, 4};
    TreeNode *root = make_tree(v);
    Solution ob;
    vector<int> result = ob.rightSideView(root);
    cout << "[";
    for (int x : result) cout << x << ", ";
    cout << "]" << endl;
    return 0;
}

ইনপুট / আউটপুট

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]