이진 트리가 하나 주어졌다고 가정해 보겠습니다. 이때 우리는 이 트리를 제자리(in-place)에서 단일 연결 리스트 형태로 변환해야 합니다. 즉, 트리의 모든 노드를 왼쪽 자식 없이 오른쪽 포인터만으로 연결된 사슬 구조처럼 만드는 것입니다.
예를 들어 다음과 같은 이진 트리가 입력으로 주어지면,
출력은 아래와 같이 오른쪽으로만 이어진 연결 리스트 형태가 됩니다.
해결 접근 방식
이 문제를 해결하려면 역방향 후위 순회(reverse post-order), 즉 오른쪽 → 왼쪽 → 노드 자신 순서로 트리를 탐색하는 것이 핵심입니다. 이렇게 하면 노드들이 전위 순회(pre-order) 순서대로 연결 리스트에 배치됩니다. 구체적인 단계는 다음과 같습니다.
포인터
prev를 null로 초기화합니다.루트 노드를 입력으로 받는 재귀 함수
solve()를 정의합니다.루트가 null이면 그대로 반환합니다.
루트의 오른쪽 서브트리에 대해 먼저
solve()를 호출합니다.그다음 루트의 왼쪽 서브트리에 대해
solve()를 호출합니다.루트의 오른쪽 포인터를
prev로 설정하고, 왼쪽 포인터는 null로 만듭니다.prev를 현재 루트로 갱신합니다.
재귀 호출이 가장 깊은 곳(오른쪽 끝)부터 되감기듯 진행되면서, 이미 처리된 노드들이 차례로 현재 노드의 오른쪽에 연결되기 때문에 결과적으로 전위 순회 순서의 연결 리스트가 완성됩니다.
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;
}
class Solution {
public:
TreeNode* prev = NULL;
void flatten(TreeNode* root) {
if(!root) return;
flatten(root->right);
flatten(root->left);
root->right = prev;
root->left = NULL;
prev = root;
}
};
main(){
vector<int> v = {1,2,5,3,4};
TreeNode *root = make_tree(v);
Solution ob;
(ob.flatten(root));
TreeNode *ptr = root;
while(ptr != NULL && ptr->val != 0){
cout << ptr->val << ", ";
ptr = ptr->right;
}
}입력
{1,2,5,3,4}출력
1, 2, 3, 4, 5,
복잡도 분석
이 알고리즘은 트리의 모든 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(n)입니다. 또한 추가적인 리스트나 배열을 사용하지 않고 기존 트리의 포인터만 재배열하기 때문에 공간 복잡도 역시 재귀 호출 스택을 제외하면 O(1)로, 진정한 의미의 제자리 변환이라고 할 수 있습니다.