C++ 문자열로부터 이진 트리 생성하기

괄호와 정수로만 구성된 문자열이 주어졌다고 가정해 봅시다. 우리는 이 문자열을 해석하여 이진 트리(binary tree)를 구성해야 합니다. 전체 입력 문자열은 하나의 이진 트리를 나타내며, 정수 뒤에는 0개, 1개 또는 2쌍의 괄호가 붙습니다. 여기서 정수는 해당 노드(루트)의 값을 의미하고, 각 괄호 쌍은 동일한 구조를 가진 자식 이진 트리를 감싸고 있습니다.

예를 들어, 입력이 "4(2(3)(1))(6(5))"라고 한다면, 출력 결과는 중위 순회(inorder traversal) 기준으로 [3, 2, 1, 4, 5, 6]이 됩니다.

해결 접근 방법

이 문제는 재귀(recursion)를 활용한 문자열 파싱으로 해결할 수 있습니다. 다음 순서대로 진행합니다.

solve() 함수를 정의합니다. 이 함수는 문자열 s와 인덱스 idx를 참조로 받습니다.
idx가 s의 길이보다 크거나 같으면 NULL을 반환합니다.
num을 빈 문자열로 초기화합니다.
idx가 s의 길이보다 작고, s[idx]가 '(' 또는 ')'가 아닌 동안 반복하며 num에 s[idx]를 추가하고 idx를 1씩 증가시킵니다. 이 과정에서 현재 노드의 정수 값을 추출합니다.
추출한 num 값(stoi 변환)으로 새 TreeNode를 생성합니다.
idx가 s의 길이보다 작고 s[idx]가 '('이라면:
- idx를 1 증가시킨 후, node->left = solve(s, idx)로 왼쪽 자식을 재귀적으로 구성합니다.
- 닫는 괄호를 건너뛰기 위해 idx를 1 증가시킵니다.
- 그 상태에서 idx가 유효하고 s[idx]가 다시 '('이라면:
  - idx를 1 증가시킨 후, node->right = solve(s, idx)로 오른쪽 자식을 재귀적으로 구성합니다.
  - 마찬가지로 idx를 1 증가시킵니다.
완성된 node를 반환합니다.

메인 호출부(str2tree)에서는 idx를 0으로 초기화한 뒤 solve(s, idx)를 호출하여 최종 루트 노드를 얻으면 됩니다.

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 inord(TreeNode *root){
   if(root != NULL){
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Solution {
public:
   TreeNode* solve(string s, int& idx){
      if (idx >= s.size())
         return NULL;
      string num = "";
      while (idx < s.size() && s[idx] != '(' && s[idx] != ')') {
         num += s[idx];
         idx++;
      }
      TreeNode* node = new TreeNode(stoi(num));
      if (idx < s.size() && s[idx] == '(') {
         idx++;
         node->left = solve(s, idx);
         idx++;
         if (idx < s.size() && s[idx] == '(') {
            idx++;
            node->right = solve(s, idx);
            idx++;
         }
      }
      return node;
   }
   TreeNode* str2tree(string s) {
      int idx = 0;
      TreeNode* temp = new TreeNode(-1);
      return solve(s, idx);
   }
};
main(){
   Solution ob;
   TreeNode *root = ob.str2tree("4(2(3)(1))(6(5))");
   inord(root);
}

입력

"4(2(3)(1))(6(5))"

출력

3 2 1 4 5 6

동작 원리 정리

이 알고리즘의 핵심은 인덱스 idx를 참조(reference)로 전달하여 재귀 호출 간에 파싱 위치를 공유한다는 점입니다. 숫자를 만나면 노드를 생성하고, 열린 괄호 '('를 만나면 왼쪽 서브트리를 먼저 재귀적으로 구성한 뒤, 두 번째 열린 괄호가 있다면 오른쪽 서브트리를 구성합니다. 닫힌 괄호 ')'를 만나면 해당 서브트리의 구성이 끝난 것이므로 상위 호출로 돌아갑니다. 시간 복잡도는 문자열 길이에 비례하여 O(n)입니다.