본문 바로가기
알고리즘/백준

백준 5639 이진 검색 트리 (JAVA 자바 풀이)

by Renechoi 2024. 11. 23.

 



https://www.acmicpc.net/problem/12873

 

📌 문제

 

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

 

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

 


⚔ 제한 사항

 

 

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

 

 

출력 

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

예시 

 

50
30
24
5
28
45
98
52
60

 

5
28
24
45
30
60
52
98
50

 


👀 문제 해석

이 문제는 이진 검색 트리(BST, Binary Search Tree)의 핵심 속성과 순회 방식을 이해해야만 풀 수 있는 전형적인 자료구조 문제이다.

 

기본적으로 전위 순회 결과를 가지고, 동일한 트리의 후위 순회 결과를 구하는 것이 목표이다.

 

문제를 풀기 위해 알아야 할 주요 개념은 다음과 같다.

 

1) 이진 검색 트리의 성질

  • 왼쪽 서브트리의 모든 값은 루트보다 작다.
  • 오른쪽 서브트리의 모든 값은 루트보다 크다.
  • 서브트리 자체도 이진 검색 트리의 조건을 만족해야 한다.

 

2) 트리 순회의 종류

  • 전위 순회(Preorder): 루트 → 왼쪽 → 오른쪽 순서로 방문한다.
  • 후위 순회(Postorder): 왼쪽 → 오른쪽 → 루트 순서로 방문한다.

이 문제는 자료구조의 기본 개념과 탐색 알고리즘에 속한다. 단순한 순서 변환 문제처럼 보일 수 있지만, 실제로는 트리 구조를 올바르게 이해하고 다루는 능력이 요구된다. 또한 입력의 크기가 최대 10,000개로 크다는 점도 주목해보아야 한다.

 

🔎 접근

1️⃣ 첫 번째 질문: "전위 순회 데이터를 배열로 다룰 수 있을까?"

처음에는 전위 순회 데이터를 기반으로 트리를 배열 형태로 다룰 수 있을지 고민했다.

 

이 방식은 구조적으로 트리를 배열에 저장한 뒤, 전위 순회를 따라 각 위치에 값을 채워 넣는 방식이다. 만약 문제의 조건에서 트리가 반드시 완전 이진 트리 형태라면 이 방식으로 풀 수 있을 것이다.

 

예를 들어, 아래와 같은 트리를 배열로 표현할 수 있다.

      50
     /  \
   30    98
  /  \   /
 24  45 52

 

이 트리를 배열로 표현하면 다음과 같을 것인데,

index:  1   2   3   4   5   6   7
value: 50  30  98  24  45  52  --

 

이처럼 완전 이진 트리의 경우 노드 간의 위치를 정규화하여 배열로 다룰 수 있다.

 

다음은 문제의 주어진 예시를 있는 그대로 구현하여 푸는 코드이다.

    private static void buildTree(int 노드위치, List<Integer> 전위순회리스트, int[] tree, Index 전위순회리스트의인덱스, int min, int max) {
        // 종료 조건: 전위 순회 리스트의 끝에 도달
        if (전위순회리스트의인덱스.value >= 전위순회리스트.size()) {
            return;
        }

        int rootValue = 전위순회리스트.get(전위순회리스트의인덱스.value);

        // 현재 값이 허용된 범위 내에 있지 않으면 리턴
        if (rootValue < min || rootValue > max) {
            return;
        }

        // 현재 값을 사용하고 인덱스를 증가시킴
        tree[노드위치] = rootValue;
        전위순회리스트의인덱스.indexUp();

        // 왼쪽 서브트리
        buildTree(노드위치 * 2, 전위순회리스트, tree, 전위순회리스트의인덱스, min, rootValue - 1);

        // 오른쪽 서브트리
        buildTree(노드위치 * 2 + 1, 전위순회리스트, tree, 전위순회리스트의인덱스, rootValue + 1, max);
    }

 

단순하게 주어진 전위 순회 리스트를 받아서 배열 기반으로 전위 순회를 따라 트리를 구성한다.

  1. 트리 구성: buildTree 함수는 전위 순회 데이터를 재귀적으로 처리해 배열의 적절한 위치에 값을 저장한다. 현재 값은 루트가 되고, 왼쪽과 오른쪽 자식은 각각 2 * 노드위치와 2 * 노드위치 + 1에 배치된다.
  2. 종료 조건: 노드 값이 허용된 범위(최소/최대)를 벗어나면 무시한다. 이진 검색 트리의 특성을 유지하기 위한 조건이다.

예를 들어 문제의 입력 조건을 살펴보면,

전위 순회 입력: 50, 30, 24, 5, 28, 45, 98, 52, 60

 

트리는 배열로 다음과 같이 표현된다.

index:  1    2    3    4    5    6    7    8    9   10   11   12   13   14   15
value:  50   30   98   24   45   52    -    5   28    -    -    -    -   60    -


문제는 주어진 요구 조건에서 트리의 형태가 완전 이진 트리가 아니라 임의의 이진 검색 트리이다.

 

예를 들어, 트리가 아래처럼 한쪽으로 치우친 경우를 고려해보자.

      50
     /
   30
  /
 24
  \
   28

 

이런 트리를 배열로 저장하려면 각 레벨의 빈 공간까지 포함해 표현해야 한다면, 필요한 배열의 공간은 얼마가 될까?

 

노드의 개수가 주어지는 상황이므로, 주어진 노드를 기반으로 거꾸로 최대 트리 크기를 계산해보자.

 

노드 개수가 (n)일 때, 트리의 높이 (h)는 다음과 같이 추정할 수 있다.


\[
h = \lceil \log_2(n+1) \rceil
\]

 

이진 트리에서 각 레벨에는 (2^k)개의 노드가 포함된다((k)는 레벨의 번호, 0부터 시작).

 

따라서, 높이 (h)인 완전 이진 트리에서 총 노드 개수는 다음과 같이 계산된다.


\[
\text{최대 노드 개수} = 2^0 + 2^1 + 2^2 + \cdots + 2^{h-1} = 2^h - 1
\]

 

주어진 노드 수 \(n\)가 있을 때, 이를 포함할 수 있는 최소 높이 \(h\)는 다음 식을 통해 계산할 수 있다.

\[
h = \lceil \log_2 (n + 1) \rceil
\]

즉, \((n+1)\)을 2의 거듭제곱으로 나눈 값의 로그를 취하고, 이를 올림(\(\lceil \cdot \rceil\))하여 높이를 구한다.

 

 

예를 들어, 노드가 3개인 경우

 

\[
h = \lceil \log_2(3 + 1) \rceil = \lceil \log_2(4) \rceil = 2
\]

배열 크기는 \((2^2 - 1 = 3)\)

 

 

      A
     / \
    B   C

 

  index:  1   2   3
  value:  A   B   C


노드가 7개인 경우

 

\[
h = \lceil \log_2(7+1) \rceil = \lceil \log_2(8) \rceil = 3
\]

배열 크기는 \(2^3 - 1 = 7\)이다.

 

        A
       / \
      B   C
     / \ / \
    D  E F  G
  index:  1   2   3   4   5   6   7
  value:  A   B   C   D   E   F   G

 

그런데 만약 완전 이진 트리가 아니라면, 배열 크기는 트리의 높이에 따라 비효율적으로 커질 수 있다.

 

예를 들어, 노드가 4개인 경우의 한쪽으로 치우친 편향 트리로 최악의 상황으로 가정해보자.

 

      A
     /
    B
   /
  C
 /
D

 

 

 

이 경우, 트리의 높이 \( h \)는 노드 개수와 같아지므로 \( h = 4 \)가 된다. 배열로 저장하기 위해 필요한 크기는 다음과 같다.

\[
\text{필요한 배열 크기} = 2^h - 1 = 2^4 - 1 = 15
\]

 

 

 

트리를 배열로 표현하면 다음과 같다.

 

index:  1   2   -   4   -   -   -   8   -   -   -   -   -   -   -
value:  A   B   -   C   -   -   -   D   -   -   -   -   -   -   -

 

따라서, 주어진 10,000개의 데이터에 대해 최악의 경우를 고려한다면, 트리의 높이 (h)는 노드 개수와 같아져 (h = 10,000)이 된다.

 

이 경우 필요한 배열의 크기는

 

\[
\text{필요한 배열 크기} = 2^{10,000} - 1
\]

 

으로, 문제 풀이가 사실상 불가능해진다.

 

그렇다면 배열로 트리를 구성하는 것은 불가능하므로 노드로 풀어볼 수 있을까?

 

2️⃣ 두 번째 질문: "노드 기반으로 트리를 구성한 후 후위 순회 결과를 구할 수 있을까?"

그렇다면 BST 구성에서 배열을 사용하지 않고 노드로 구성한다면 가능할까? 아이디어는 간단하다.

  • 전위 순회의 첫 번째 값은 루트 노드이다.
  • 이후 값들은 루트보다 작은 값은 왼쪽 서브트리, 루트보다 큰 값은 오른쪽 서브트리에 위치한다.
  • 이 규칙을 반복적으로 적용하면 전위 순회 데이터를 활용해 BST를 재구성할 수 있다.
  • 이렇게 구성한 트리에서 후위 순회를 수행하면 최종 결과를 얻을 수 있다.

그렇다면 노드는 이렇게 구성할 수 있을 것이다.

 

1) 루트 찾기

  • 전위 순회의 첫 번째 값이 트리의 루트가 된다.
  • 예시에서 전위 순회 데이터 50, 30, 24, 5, 28, 45, 98, 52, 60을 보면 50이 루트이다.

 

2) 서브트리 분리

  • 이후 값 중 50보다 작은 값들은 루트의 왼쪽 서브트리에, 큰 값들은 오른쪽 서브트리에 들어간다.
  • 따라서 30, 24, 5, 28, 45는 왼쪽 서브트리, 98, 52, 60은 오른쪽 서브트리에 속한다.

 

3) 재귀적 처리

  • 왼쪽 서브트리와 오른쪽 서브트리에 대해 같은 과정을 반복한다. 이를 통해 트리가 완성된다.

다음과 같이 노드를 설정하자.

static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
}


재귀 함수의 종료 조건

먼저 재귀 호출의 종료 조건을 생각해보자. 종료 조건은 다음과 같은 두 가지 상황에서 발생한다.

 

1) 전위 순회 리스트를 모두 탐색한 경우

  • 현재 처리 중인 인덱스가 전위 순회 리스트의 크기를 넘어가면, 더 이상 트리에 추가할 노드가 없으므로 종료한다.

 

2) 현재 값이 허용된 범위를 벗어난 경우

  • 이진 검색 트리의 규칙에 따라, 서브트리에 속하는 값은 루트 값에 따라 최소값(min)과 최대값(max) 범위 내에 있어야 한다. 범위를 벗어난 값은 해당 서브트리에 속할 수 없으므로, 재귀 호출을 종료한다.
if (index.value >= 전위순회리스트.size()) {
    return null; // 전위 순회 리스트를 모두 탐색한 경우
}

int rootValue = 전위순회리스트.get(index.value);

// 현재 값이 허용된 범위를 벗어나면 리턴
if (rootValue < min || rootValue > max) {
    return null;
}


루트 노드 구성

그 다음, 재귀적으로 트리를 구성하는 과정의 첫 단계로 루트 노드 생성하자. 현재 전위 순회 리스트에서 처리 중인 값을 루트로 설정하며, 이를 TreeNode 객체로 생성한다. 그리고 루트 노드를 생성한 뒤, 다음 값을 처리하도록 인덱스를 증가시킨다.

 

여기서 인덱스는 문제에서 주어진 전위 순회 리스트의 값들을 가져오기 위해 사용된다.

index.indexUp(); // 현재 값을 사용하고 다음 인덱스로 이동
TreeNode root = new TreeNode(rootValue); // 루트 노드 생성


예시 데이터를 적용해보면

  • 전위 순회 리스트: 50, 30, 24, 5, 28, 45, 98, 52, 60
  • 첫 번째 호출에서 루트 값은 50으로 설정될 것이며, 이후 값을 가져오기 위해 인덱스는 1로 증가한다.


왼쪽 서브트리와 오른쪽 서브트리 구성

이제 재귀 함수의 핵심이 되는 부분을 살펴보자. 이진 검색 트리의 특징에 따라,

  • 왼쪽 서브트리는 루트 값보다 작은 값을 포함하며, 범위는 min에서 rootValue - 1이다.
  • 오른쪽 서브트리는 루트 값보다 큰 값을 포함하며, 범위는 rootValue + 1에서 max이다.

이를 재귀적으로 호출하여 트리를 구성한다.

// 왼쪽 서브트리 생성 (루트 값보다 작은 값)
root.left = buildTree(전위순회리스트, index, min, rootValue - 1);

// 오른쪽 서브트리 생성 (루트 값보다 큰 값)
root.right = buildTree(전위순회리스트, index, rootValue + 1, max);


왼쪽 서브트리와 오른쪽 서브트리 구성

이제 재귀 함수의 핵심이 되는 부분을 살펴보자. 이진 검색 트리의 특징에 따라,

  • 왼쪽 서브트리는 루트 값보다 작은 값을 포함하며, 범위는 min에서 rootValue - 1이다.
  • 오른쪽 서브트리는 루트 값보다 큰 값을 포함하며, 범위는 rootValue + 1에서 max이다.

이를 재귀적으로 호출하여 트리를 구성한다.

// 왼쪽 서브트리 생성 (루트 값보다 작은 값)
root.left = buildTree(전위순회리스트, index, min, rootValue - 1);

// 오른쪽 서브트리 생성 (루트 값보다 큰 값)
root.right = buildTree(전위순회리스트, index, rootValue + 1, max);


여기서 buildTree 함수는 재귀적으로 호출되면서 하위 트리를 구성하고, 이를 반환하여 부모 노드의 left와 right에 매핑한다.

여기서 중요한 점은, 매핑은 재귀 함수가 호출되는 시점에 이루어지는 것이 아니라, 재귀 호출이 종료되어 반환될 때 이루어진다는 것이다. 즉, root.left와 root.right에 실제 노드가 매핑되는 것은 하위 재귀 호출이 반환된 이후에 발생한다.

 

매핑 과정: 재귀 호출 종료 후 연결

재귀적으로 buildTree 함수가 호출되면, 먼저 왼쪽 서브트리와 오른쪽 서브트리를 각각 처리하기 위해 추가적인 호출이 이루어진다.

 

그러나 반환된 값을 통해 left와 right가 설정되는 것은 각 호출의 종료 조건을 만족한 후이다. 즉, 하위 서브트리가 완전히 처리된 다음에야 상위 노드와 연결된다.

 

간단한 데이터로 매핑 플로우 따라가보자.

 

전위 순회 데이터: 50, 30, 24, 70


1. 첫 번째 호출 (root = 50)
  • 현재 값: 50 (루트)
  • 왼쪽 서브트리: buildTree(전위순회리스트, index, Integer.MIN_VALUE, 49) 호출
  • 오른쪽 서브트리: buildTree(전위순회리스트, index, 51, Integer.MAX_VALUE) 호출

매핑은 아직 이루어지지 않고, 재귀 호출로 내려간다.

2. 두 번째 호출 (왼쪽 서브트리) (root = 30)
  • 현재 값: 30
  • 왼쪽 서브트리: buildTree(전위순회리스트, index, Integer.MIN_VALUE, 29) 호출
  • 오른쪽 서브트리: buildTree(전위순회리스트, index, 31, 49) 호출

여전히 매핑은 이루어지지 않고, 하위 재귀 호출로 내려간다.

3. 세 번째 호출 (왼쪽의 왼쪽 서브트리) (root = 24)
  • 현재 값: 24
  • 왼쪽 서브트리: buildTree(전위순회리스트, index, Integer.MIN_VALUE, 23) 호출 → 종료 조건 충족 → null 반환
  • 오른쪽 서브트리: buildTree(전위순회리스트, index, 25, 29) 호출 → 종료 조건 충족 → null 반환

이제 null 반환 후 root = 24가 완전히 처리되었으므로, 상위 호출(root = 30)로 돌아가 30.left = 24로 매핑된다.

4. 두 번째 호출의 오른쪽 서브트리로 복귀
  • 현재 값: 30의 오른쪽 서브트리 처리
  • 범위를 벗어난 값 (31 <= 30 <= 49) → null 반환

이제 상위 호출(root = 50)로 돌아가, 50.left = 30으로 매핑된다.

5. 첫 번째 호출의 오른쪽 서브트리로 이동 (root = 70)
  • 현재 값: 70
  • 왼쪽 서브트리: buildTree(전위순회리스트, index, 51, 69) 호출 → 종료 조건 충족 → null 반환
  • 오른쪽 서브트리: buildTree(전위순회리스트, index, 71, Integer.MAX_VALUE) 호출 → 종료 조건 충족 → null 반환

null 반환 후 50.right = 70로 매핑된다.

 

이와 같은 과정에 대해 호출 스택으로 살펴보면 다음과 같다.

 

1. buildTree(전위순회리스트, index=0, min=Integer.MIN_VALUE, max=Integer.MAX_VALUE)
---------------------------------------------------------------------------------
   호출: root = 50 (루트 노드)
   왼쪽 서브트리: buildTree(전위순회리스트, index=1, min=Integer.MIN_VALUE, max=49)
   오른쪽 서브트리: buildTree(전위순회리스트, index=3, min=51, max=Integer.MAX_VALUE)

   ↓

   2. buildTree(전위순회리스트, index=1, min=Integer.MIN_VALUE, max=49)
   ---------------------------------------------------------------
      호출: root = 30 (루트의 왼쪽 자식)
      왼쪽 서브트리: buildTree(전위순회리스트, index=2, min=Integer.MIN_VALUE, max=29)
      오른쪽 서브트리: buildTree(전위순회리스트, index=3, min=31, max=49)

      ↓

      3. buildTree(전위순회리스트, index=2, min=Integer.MIN_VALUE, max=29)
      ------------------------------------------------------------
         호출: root = 24 (루트의 왼쪽 서브트리)
         왼쪽 서브트리: buildTree(전위순회리스트, index=3, min=Integer.MIN_VALUE, max=23) → 종료 조건 충족 → null 반환
         오른쪽 서브트리: buildTree(전위순회리스트, index=3, min=25, max=29) → 종료 조건 충족 → null 반환

         반환: TreeNode(24)
      ------------------------------------------------------------
      ↑ 반환된 값: `24`가 `root.left`에 매핑.

   반환: TreeNode(30, left=TreeNode(24), right=null)
   ---------------------------------------------------------------
   ↑ 반환된 값: `30`이 `root.left`에 매핑.

   3. buildTree(전위순회리스트, index=3, min=51, max=Integer.MAX_VALUE)
   ------------------------------------------------------------
      호출: root = 70 (루트의 오른쪽 자식)
      왼쪽 서브트리: buildTree(전위순회리스트, index=4, min=51, max=69) → 종료 조건 충족 → null 반환
      오른쪽 서브트리: buildTree(전위순회리스트, index=4, min=71, max=Integer.MAX_VALUE) → 종료 조건 충족 → null 반환

      반환: TreeNode(70)
   ------------------------------------------------------------
   ↑ 반환된 값: `70`이 `root.right`에 매핑.

반환: TreeNode(50, left=TreeNode(30, left=TreeNode(24), right=null), right=TreeNode(70))
---------------------------------------------------------------------------------


최종 트리

       50
      /  \
    30    70
   /
 24


이와 같은 방식으로 트리를 구성하면 이제 후위 순회로 출력 해주기만 하면 된다.

    private static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.value);
    }


이 방식으로 제출했을 때 통과할 수 있다.

 

3️⃣ 세 번째 질문: "트리를 구성하지 않고도 후위 순회 결과를 구할 수 있을까?"

그런데 한번 더 생각해보자.

 

트리를 생성하지 않아도, 전위 순회 데이터의 규칙을 활용하면 가능하지 않을까?

  • 전위 순회 결과를 이용해 서브트리의 경계를 파악한다.
  • 재귀적으로 좌우 서브트리를 처리하면서 후위 순회 순서를 생성한다.
  • 루트 노드는 항상 좌우 서브트리를 처리한 뒤 마지막에 추가된다.

여기서 핵심은 "경계를 파악한다"는 개념이다.

 

이 말은 전위 순회 데이터에서 왼쪽 서브트리와 오른쪽 서브트리를 구분하는 기준을 찾는다는 의미이다.

 

전위 순회 데이터는 항상 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 나온다. 따라서,

  • 첫 번째 값은 항상 루트이다.
  • 루트보다 작은 값들은 모두 왼쪽 서브트리에 속한다.
  • 루트보다 큰 값들은 모두 오른쪽 서브트리에 속한다.

루트보다 작은 값들이 끝나는 지점, 즉 root를 기준으로, 처음으로 루트보다 큰 값이 나타나는 위치가 오른쪽 서브트리의 시작 경계이다.

 

이를 코드로 구현하면 다음과 같다.

 

// 서브트리 경계를 찾는 코드
int boundary = start + 1;
while (boundary <= end && preorder.get(boundary) < root) {
    boundary++;
}
  • boundary는 start + 1부터 시작한다. (start는 루트 위치)
  • preorder[boundary] 값이 root보다 작으면 왼쪽 서브트리에 속하므로 boundary++로 이동한다.
  • root보다 큰 값을 만나면 루프를 종료한다. 그 위치가 오른쪽 서브트리의 시작이다.

예를 들어서 다음과 같은 데이터를 보자.

 

preorder = [50, 30, 24, 70]

 

| 인덱스 | 값  | 조건 (값 < 50) | 서브트리 |
|--------|------|----------------|----------|
| 0      | 50   | ❌             | 루트     |
| 1      | 30   | ✅             | 왼쪽     |
| 2      | 24   | ✅             | 왼쪽     |
| 3      | 70   | ❌             | 오른쪽     |

 

이렇게 분할되는 코드를 어떻게 트리 구성 없이 후위 순회를 할 수 있다는 것일까?

 

코드는 다음과 같다.

 

private static void generatePostOrder(List<Integer> 전위순회리스트, int start, int end, List<Integer> 결과) {
    // 종료 조건: 구간이 비어 있으면 반환
    if (start > end) {
        return;
    }

    // 현재 구간의 첫 번째 값이 루트
    int rootValue = 전위순회리스트.get(start);

    // 루트보다 큰 값이 나오는 첫 번째 인덱스를 찾아 서브트리 경계 설정
    int rightSubtreeIndex = start + 1;
    while (rightSubtreeIndex <= end && 전위순회리스트.get(rightSubtreeIndex) < rootValue) {
        rightSubtreeIndex++;
    }

    // 왼쪽 서브트리 처리
    generatePostOrder(전위순회리스트, start + 1, rightSubtreeIndex - 1, 결과);

    // 오른쪽 서브트리 처리
    generatePostOrder(전위순회리스트, rightSubtreeIndex, end, 결과);

    // 루트 추가 (후위 순회에서 마지막 처리)
    결과.add(rootValue);
}

 

전위 순회는 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 데이터를 나열한다.

 

따라서,

  1. 첫 번째 값이 항상 루트이다.
  2. 루트 값보다 작은 값들은 왼쪽 서브트리에 속하고, 큰 값들은 오른쪽 서브트리에 속한다.
  3. 루트보다 작은 값이 끝나는 지점(경계)을 찾으면 서브트리의 구간을 알 수 있다.

한편, 후위 순회는 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서이다.

 

이를 바탕으로,

  1. 먼저 왼쪽 서브트리를 처리한다.
  2. 이어서 오른쪽 서브트리를 처리한다.
  3. 마지막에 루트 값을 추가하면 후위 순회 결과를 얻을 수 있다.

이때, 전위 순회 데이터를 구간(start와 end)으로 나누고, 이를 재귀적으로 처리한다.

  • 경계값(boundary)을 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 구분한다.
  • 구간이 비어 있으면(종료 조건) 재귀를 종료한다.
  • 각 호출이 끝날 때 루트 값을 결과 리스트에 추가한다.

여기서 "호출이 끝날 때 루트 값을 리스트에 추가한다"는 이유는 후위 순회(Postorder Traversal)의 규칙에 따른 작업 때문이다.

 

함수 호출은 "자식 노드를 모두 처리한 후"에 부모 노드로 돌아온다. 따라서 재귀적으로 왼쪽과 오른쪽 서브트리를 모두 처리한 후, 현재 호출이 다루는 루트 노드를 리스트에 추가하는 방식으로 후위 순회를 구현하는 것이다.

 

즉, 루트 값은 왼쪽과 오른쪽 서브트리가 처리된 이후에 가장 마지막에 처리되어야 하므로, 모든 서브트리 호출이 종료된 후, 마지막으로 현재 호출에서 처리 중인 루트 값을 결과 리스트에 추가한다.

첫 번째 호출

generatePostorder(preorder, start=0, end=3, postorder=[])
---------------------------------------------------------
- root = preorder[0] = 50
- 경계(boundary):
    preorder[1] = 30 → 30 < 50 → boundary++
    preorder[2] = 24 → 24 < 50 → boundary++
    preorder[3] = 70 → 70 > 50 → boundary = 3
- 왼쪽 서브트리: start+1 = 1, boundary-1 = 2 → [30, 24]
- 오른쪽 서브트리: boundary = 3, end = 3 → [70]
---------------------------------------------------------
재귀 호출:
1. 왼쪽 서브트리: generatePostorder(preorder, start=1, end=2, postorder=[])
2. 오른쪽 서브트리: generatePostorder(preorder, start=3, end=3, postorder=[])

두 번째 호출 (왼쪽 서브트리)

generatePostorder(preorder, start=1, end=2, postorder=[])
---------------------------------------------------------
- root = preorder[1] = 30
- 경계(boundary):
    preorder[2] = 24 → 24 < 30 → boundary++
    boundary = 3 (end+1)
- 왼쪽 서브트리: start+1 = 2, boundary-1 = 2 → [24]
- 오른쪽 서브트리: boundary = 3, end = 2 → 없음
---------------------------------------------------------
재귀 호출:
1. 왼쪽 서브트리: generatePostorder(preorder, start=2, end=2, postorder=[])
2. 오른쪽 서브트리: 없음 (종료 조건 충족)

세 번째 호출 (왼쪽의 왼쪽 서브트리)

generatePostorder(preorder, start=2, end=2, postorder=[])
---------------------------------------------------------
- root = preorder[2] = 24
- 경계(boundary): start+1 = 3 > end = 2 → 종료 조건 충족
- 왼쪽 서브트리: 없음
- 오른쪽 서브트리: 없음
---------------------------------------------------------
루트 추가: postorder = [24]
반환: postorder = [24]

두 번째 호출 반환 후

- 왼쪽 서브트리 처리 완료: postorder = [24]
- 오른쪽 서브트리: 없음 (종료 조건 충족)
- 루트 추가: postorder = [24, 30]
반환: postorder = [24, 30]

첫 번째 호출 반환 후

- 왼쪽 서브트리 처리 완료: postorder = [24, 30]
- 오른쪽 서브트리 호출:
generatePostorder(preorder, start=3, end=3, postorder=[24, 30])

세 번째 호출 (오른쪽 서브트리)

generatePostorder(preorder, start=3, end=3, postorder=[24, 30])
---------------------------------------------------------
- root = preorder[3] = 70
- 경계(boundary): start+1 = 4 > end = 3 → 종료 조건 충족
- 왼쪽 서브트리: 없음
- 오른쪽 서브트리: 없음
---------------------------------------------------------
루트 추가: postorder = [24, 30, 70]
반환: postorder = [24, 30, 70]

최종 반환

- 왼쪽 서브트리 처리 완료: postorder = [24, 30]
- 오른쪽 서브트리 처리 완료: postorder = [24, 30, 70]
- 루트 추가: postorder = [24, 30, 70, 50]

최종 후위 순회 결과

[24, 30, 70, 50]

시각화된 호출 스택

호출 스택 구조

1. generatePostorder(preorder, start=0, end=3) -> root = 50
   ├── generatePostorder(preorder, start=1, end=2) -> root = 30
   │    ├── generatePostorder(preorder, start=2, end=2) -> root = 24 (리프 노드)
   │    └── [루트 추가: 30]
   └── generatePostorder(preorder, start=3, end=3) -> root = 70 (리프 노드)
        └── [루트 추가: 70]
[루트 추가: 50]

 

이 접근법의 핵심은 트리의 구조를 데이터를 분할하는 방식으로 표현하는 데 있다.

 

트리를 명시적으로 생성하는 대신, 서브트리 경계를 기준으로 문제를 해결함으로써 효율성을 높일 수 있다.

반응형
저작자표시 비영리 변경금지

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 기념품 (자바 풀이)  (4) 2024.10.12
[백준] 앵무새 (자바 풀이 - 큐, 배열, 해시맵을 곁들인)  (1) 2024.10.12
[백준] 좋은 친구 (자바 풀이)  (0) 2024.10.11
[백준] 히스토그램에서 가장 큰 직사각형 (자바 풀이)  (0) 2024.10.05
백준 5397 키 로거 (JAVA 자바 풀이)  (0) 2024.01.03

관련글

티스토리툴바