이진 트리가 하나 있다고 가정해 보겠습니다. 우리는 루트 노드에서 시작하여 전위(preorder) 깊이 우선 탐색(DFS)을 수행합니다.
탐색 과정에서 각 노드를 방문할 때마다 해당 노드의 깊이(D)만큼 대시(-)를 출력한 뒤, 그 다음에 노드의 값을 출력합니다. 노드의 깊이가 D라면 그 직계 자식의 깊이는 D+1이 되고, 루트 노드의 깊이는 0입니다.
또 한 가지 중요한 조건이 있습니다. 어떤 노드에 자식이 하나만 있다면, 그 자식은 반드시 왼쪽 자식이라는 점입니다. 따라서 위 규칙에 따라 생성된 탐색 결과 문자열 S가 주어졌을 때, 원래의 트리를 복원하고 그 루트 노드를 반환해야 합니다.
예를 들어 입력이 "1-2--3--4-5--6--7"과 같다면, 복구된 트리는 다음과 같습니다.
해결 방법
이 문제는 스택(stack)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 대시(-)의 개수로 각 노드의 깊이를 파악하고, 스택의 크기를 현재 깊이에 맞게 조정하면서 부모-자식 관계를 연결하는 것입니다. 알고리즘 단계는 다음과 같습니다.
스택 st를 하나 정의합니다.
i := 0, n := 문자열 S의 길이로 초기화합니다.
lvl := 0, num := 0으로 초기화합니다.
i < n인 동안 다음을 반복합니다.
S[i]가 '-'인 동안 lvl을 1씩 증가시키고 i를 1씩 증가시켜 현재 노드의 깊이를 구합니다.
num := 0으로 초기화합니다.
i < n이고 S[i]가 '-'가 아닌 동안 num = num * 10 + (S[i] - '0')을 수행하여 연속된 숫자를 하나의 값으로 만들고 i를 증가시킵니다.
스택의 크기가 lvl보다 큰 동안 스택에서 요소를 제거(pop)합니다. 이렇게 하면 스택에는 현재 노드의 조상들만 남게 됩니다.
num 값을 가지는 새로운 트리 노드 temp를 생성합니다.
스택이 비어 있지 않고 스택 최상단 노드의 왼쪽 자식이 NULL이라면, 그 왼쪽 자식을 temp로 설정합니다.
그렇지 않고 스택이 비어 있지 않다면, 스택 최상단 노드의 오른쪽 자식을 temp로 설정합니다.
temp를 스택에 삽입(push)합니다.
모든 문자를 처리한 후, 스택의 크기가 1보다 큰 동안 요소를 제거합니다.
스택이 비어 있으면 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 inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
stack<TreeNode*> st;
int i = 0;
int n = S.size();
int lvl = 0;
int num = 0;
while (i < n) {
for (lvl = 0; S[i] == '-'; lvl++, i++)
;
num = 0;
while (i < n && S[i] != '-') {
num = num * 10 + (S[i] - '0');
i++;
}
while (st.size() > lvl)
st.pop();
TreeNode* temp = new TreeNode(num);
if (!st.empty() && !st.top()->left) {
st.top()->left = temp;
}
else if (!st.empty()) {
st.top()->right = temp;
}
st.push(temp);
}
while (st.size() > 1)
st.pop();
return st.empty() ? NULL : st.top();
}
};
main(){
Solution ob;
TreeNode *root = ob.recoverFromPreorder("1-2--3--4-5--6--7");
inord(root);
}입력
"1-2--3--4-5--6--7"
출력
3 2 4 1 6 5 7