이진 트리가 하나 주어졌다고 가정해 봅시다. 우리의 목표는 이 트리를 제자리(in-place)에서 연결 리스트 형태로 평탄화(flatten)하는 것입니다.
예를 들어 다음과 같은 트리가 있다면 −
평탄화 작업이 끝난 후 출력되는 트리는 아래와 같은 모습이 됩니다. 모든 노드가 오른쪽 포인터를 따라 일렬로 연결된 형태입니다.
해결 접근 방식
이 문제는 역방향 후위 순회(reverse post-order traversal)를 활용하면 우아하게 해결할 수 있습니다. 핵심 아이디어는 오른쪽 서브트리부터 먼저 처리한 뒤 왼쪽 서브트리를 처리하면서, 각 노드를 이전에 방문한 노드(prev)의 뒤에 연결하는 것입니다. 구체적인 단계는 다음과 같습니다.
포인터
prev를null로 초기화합니다.루트 노드를 입력으로 받는 재귀 함수
solve()(또는flatten())를 정의합니다.현재 노드(root)가
null이면 그대로 반환합니다.먼저 오른쪽 자식에 대해 재귀 호출을 수행합니다.
그다음 왼쪽 자식에 대해 재귀 호출을 수행합니다.
현재 노드의 오른쪽 포인터를
prev로 설정하고, 왼쪽 포인터는null로 만듭니다.prev를 현재 노드로 갱신합니다.
오른쪽부터 순회하기 때문에 재귀가 되감기는 시점에는 이미 하위 노드들이 모두 연결된 상태가 되며, 각 노드는 자연스럽게 자신보다 나중에 방문된 노드를 오른쪽으로 가리키게 됩니다. 이 방식은 추가 공간 없이 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
예제 코드 (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)입니다. 역방향 후위 순회라는 직관적이지 않을 수 있는 순서를 사용한다는 점이 이 풀이의 핵심 포인트입니다.