C++ में बाइनरी ट्री अपसाइड डाउन

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

इसलिए, अगर इनपुट [1,2,3,4,5]

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

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

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह नोड, बराबर, भाई,

  ले जाएगा

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

  • वापसी शून्य

• बच्चा =नोड के बाईं ओर

• 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]