C++-এ বাইনারি ট্রি আপসাইড ডাউন

একটি বাইনারি ট্রি দেওয়া আছে যেখানে সব ডান নোড إما লিফ নোড (সিবলিংসহ) অথবা খালি। এই ট্রিকে আপসাইড ডাউন ফ্লিপ করে এমন একটি ট্রি বানাতে হবে যেখানে মূল ডান নোডগুলো বাম লিফ নোডে রূপান্তরিত হয়। নতুন রুট রিটার্ন করতে হবে।

ইনপুট: [1,2,3,4,5]

আউটপুট: [4,5,2,null,null,3,1]

সমাধানের ধাপগুলো (রিকার্সিভ):

• solve(node, parent, sibling) ফাংশন ডিফাইন করব

• বেস কেস: নোড না থাকলে NULL রিটার্ন

• child = node->left, currSib = node->right

• node->left = sibling, node->right = parent (রিভার্স লিংক)

• যদি child ও currSib দুটোই নেই, তবে node রিটার্ন (নতুন রুট)

• return solve(child, node, currSib)

• মেইন থেকে solve(root, NULL, NULL) কল করব

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন −

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

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

void insert(TreeNode **root, int val) {
    queue 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;
}

void inord(TreeNode *root) {
    if(root != NULL) {
        inord(root->left);
        cout << root->val << " ";
        inord(root->right);
    }
}

class Solution {
public:
    TreeNode* solve(TreeNode* node, TreeNode* par, TreeNode* sibling) {
        if (!node || node->val == 0)
            return NULL;
        TreeNode* child = node->left;
        TreeNode* currSib = node->right;
        node->left = sibling;
        node->right = par;
        if (!child && !currSib)
            return node;
        return solve(child, node, currSib);
    }
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        return solve(root, NULL, NULL);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4,5};
    TreeNode *root = make_tree(v);
    inord(ob.upsideDownBinaryTree(root));
}

ইনপুট

[1,2,3,4,5]

আউটপুট

[4,5,2,null,null,3,1]