C++ में बाइनरी ट्री को उल्टा करना

मान लीजिए हमारे पास एक बाइनरी ट्री है जहां सभी दाएं नोड्स या तो लीफ नोड्स हैं जिनका एक सिबलिंग है अन्यथा खाली हैं, हमें इसे उल्टा करके एक ऐसा ट्री बनाना है जहां मूल दाएं नोड्स बाएं लीफ नोड्स में बदल जाएं। हमें नया नोड लौटाना है।

इसलिए, यदि इनपुट है [1,2,3,4,5]

तो आउटपुट बाइनरी ट्री [4,5,2,#,#,3,1] का रूट लौटाएगा

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• एक फ़ंक्शन solve() परिभाषित करें, जो node, par, sibling लेगा,

• यदि node मौजूद नहीं है, तो -

  • NULL लौटाएं

• child = node का बायाँ भाग

• currSib = node का दायाँ भाग

• node := sibling का बायाँ भाग

• node := par का दायाँ भाग

• यदि child और currSib मौजूद नहीं हैं, तो -

  • node लौटाएं

• 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);    } }; 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]