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)을 호출하여 최종 결과를 얻습니다.

예제 구현

아래 C++ 구현 예시를 살펴보면 동작 원리를 더 잘 이해할 수 있습니다.

#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<TreeNode*> 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);
    }
};
int 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]