ধরুন আমাদের একটি বাইনারি গাছ আছে যেখানে সমস্ত ডান নোডগুলি হয় লিফ নোড সহ একটি ভাইবোন অন্যথায় খালি, আমাদের এটিকে উল্টাতে হবে এবং এটিকে একটি গাছে পরিণত করতে হবে যেখানে আসল ডান নোডগুলি বাম পাতার নোডে পরিণত হয়েছে। আমাদের নতুন নোড ফেরত দিতে হবে।
সুতরাং, যদি ইনপুটটি [1,2,3,4,5]
এর মত হয়
তারপর আউটপুট বাইনারি ট্রি [4,5,2,#,#,3,1]
এর রুট ফিরিয়ে দেবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি নোড, পার, ভাইবোন,
নেবে -
যদি নোড উপস্থিত না থাকে, তাহলে -
-
রিটার্ন NULL
-
-
শিশু =নোডের বাম
-
currSib =নোডের ডানদিকে
-
নোড :=ভাইবোনের বাম
-
নোড :=সমমানের অধিকার
-
যদি শিশু এবং currSib উপস্থিত না থাকে, তাহলে -
-
রিটার্ন নোড
-
-
রিটার্ন সলভ (শিশু, নোড, currSib)
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
রিটার্ন সলভ (রুট, শূন্য, শূন্য)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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);
}
};
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]
