Cây nhị phân Upside Down trong C ++

Giả sử chúng ta có một cây nhị phân trong đó tất cả các nút bên phải hoặc là các nút lá với một anh em khác trống, chúng ta phải lật ngược nó và biến nó thành một cây mà các nút bên phải ban đầu biến thành các nút lá bên trái. Chúng tôi phải trả lại nút mới.

Vì vậy, nếu đầu vào là [1,2,3,4,5]

thì đầu ra sẽ trả về gốc của cây nhị phân [4,5,2, #, #, 3,1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm giải quyết (), điều này sẽ lấy nút, mệnh, anh chị em,

• nếu nút không có, thì -

  • trả về NULL

• con =bên trái của nút

• currSib =bên phải của nút

• node:=left of anh chị em

• node:=right of par

• nếu không có child và currSib thì -

  • nút trả lại

• trả về giải quyết (con, nút, currSib)

• Từ phương thức chính, hãy làm như sau -

• trả về giải quyết (gốc, NULL, NULL)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[1,2,3,4,5]

Đầu ra

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