C++에서 거꾸로 된 이진 트리

모든 오른쪽 노드가 형제가 있는 리프 노드이거나 비어 있는 이진 트리가 있다고 가정하면 이를 거꾸로 뒤집어 원래 오른쪽 노드가 왼쪽 리프 노드로 바뀌는 트리로 바꿔야 합니다. 새 노드를 반환해야 합니다.

따라서 입력이 [1,2,3,4,5]

그러면 출력은 이진 트리 [4,5,2,#,#,3,1]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve() 함수를 정의하면 노드, 파, 형제,

  가 사용됩니다.

• 노드가 없으면 -

  • NULL 반환

• 자식 =노드의 왼쪽

• currSib =노드의 오른쪽

• 노드 :=형제의 왼쪽

• node :=par

  의 오른쪽

• 자식 및 currSib이 없으면 -

  • 반환 노드

• 해결 반환(자식, 노드, currSib)

• 주요 방법에서 다음을 수행하십시오 -

• 해결(루트, 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]