트리의 순회-7.13(대강 돌아가는 것만 봄)

류한선·2025년 6월 17일

실기연습-2

목록 보기

2/95

좋아요! 백준 2263번 "트리의 순회" 문제는 중위 순회(Inorder) 와 후위 순회(Postorder) 가 주어졌을 때, 전위 순회(Preorder) 결과를 구하는 문제입니다.

🧠 문제 개요 (요약)

입력:
1. 트리의 노드 개수 n
2. 중위 순회 결과 inorder[]
3. 후위 순회 결과 postorder[]
출력: 전위 순회 결과 preorder[]

🧪 예제 입력 (내가 정함)

입력:
7
4 2 5 1 6 3 7
4 5 2 6 7 3 1

출력:
1 2 4 5 3 6 7

📌 이 트리는 이렇게 생겼습니다:

✅ 전체 Java 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] inorder, postorder;
    static int[] indexInInorder;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        // 입력을 빠르게 받기 위해 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 노드 수

        inorder = new int[n];
        postorder = new int[n];
        indexInInorder = new int[100001]; // 값의 위치를 저장

        // 중위 순회 입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            inorder[i] = Integer.parseInt(st.nextToken());
            indexInInorder[inorder[i]] = i;
        }

        // 후위 순회 입력 받기
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            postorder[i] = Integer.parseInt(st.nextToken());
        }

        // 재귀 호출 시작
        buildPreOrder(0, n - 1, 0, n - 1);

        System.out.println(sb.toString());
    }

    static void buildPreOrder(int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) return;

        // 후위 순회의 마지막 원소는 현재 서브트리의 루트이다.
        int root = postorder[postEnd];
        sb.append(root).append(" ");

        // 루트의 위치를 중위 순회에서 찾는다.
        int rootIndex = indexInInorder[root];

        // 왼쪽 서브트리의 노드 수 계산
        int leftSize = rootIndex - inStart;

        // 왼쪽 서브트리 재귀 호출
        buildPreOrder(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);

        // 오른쪽 서브트리 재귀 호출
        buildPreOrder(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
    }
}

🔬 코드 한 줄씩 분석 + 예제 기반 흐름

예제 입력:

n = 7
inorder =    4 2 5 1 6 3 7
postorder =  4 5 2 6 7 3 1

(1) 입력 받기 부분

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

역할: 노드 개수 입력
실행 결과: n = 7

inorder = new int[n];
postorder = new int[n];
indexInInorder = new int[100001];

역할: 배열 초기화
이유: 값을 O(1)로 찾아야 하므로 indexInInorder는 값 → 인덱스를 빠르게 찾기 위한 용도

// 중위 순회 배열 입력받기
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
    inorder[i] = Integer.parseInt(st.nextToken());
    indexInInorder[inorder[i]] = i;
}

📌 입력:

4 2 5 1 6 3 7

결과:

inorder = [4,2,5,1,6,3,7]
indexInInorder[4] = 0
indexInInorder[2] = 1
indexInInorder[5] = 2
...

// 후위 순회 배열 입력받기
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
    postorder[i] = Integer.parseInt(st.nextToken());
}

📌 입력:

4 5 2 6 7 3 1

결과:

postorder = [4,5,2,6,7,3,1]

(2) 트리 재구성 및 전위 순회 출력 함수 호출

buildPreOrder(0, n - 1, 0, n - 1);

🌲 buildPreOrder 함수 상세 흐름 (재귀)

1차 호출: `buildPreOrder(0,6,0,6)`

중위: 4 2 5 1 6 3 7
후위: 4 5 2 6 7 3 1
후위 끝: 1 → root
indexInInorder[1] = 3 → 중위에서 root 인덱스
leftSize = 3 → 왼쪽 노드 수

전위 출력: 1

왼쪽 트리 재귀: `buildPreOrder(0,2,0,2)`

후위 마지막: 2
중위에서 2의 위치: 1
leftSize = 1

전위 출력: 1 2

왼쪽 자식: `buildPreOrder(0,0,0,0)` → root=4

전위: 1 2 4

오른쪽 자식: `buildPreOrder(2,2,1,1)` → root=5

전위: 1 2 4 5

오른쪽 트리 재귀: `buildPreOrder(4,6,3,5)`

후위 끝: 3 → root
index = 5
leftSize = 1

전위: 1 2 4 5 3

왼쪽 자식: `buildPreOrder(4,4,3,3)` → root=6

전위: 1 2 4 5 3 6

오른쪽 자식: `buildPreOrder(6,6,4,4)` → root=7

전위: 1 2 4 5 3 6 7

✅ 최종 출력

1 2 4 5 3 6 7

좋아요! 지금부터 buildPreOrder() 메서드를 예제를 따라가며 완전히 디버깅하듯 한 줄씩, 어떻게 동작하는지를 해부하겠습니다.

📌 메서드 원형 다시 보기:

static void buildPreOrder(int inStart, int inEnd, int postStart, int postEnd)

각 매개변수 의미:

inStart, inEnd: 현재 중위 순회(inorder)에서 탐색할 구간
postStart, postEnd: 현재 후위 순회(postorder)에서 탐색할 구간

📥 입력 예제 복습:

inorder    = [4, 2, 5, 1, 6, 3, 7]
postorder  = [4, 5, 2, 6, 7, 3, 1]

📌 우리가 만들고자 하는 전위 순회 결과:

1 2 4 5 3 6 7

🔍 전체 흐름을 따라가며 디버깅

🔁 1차 호출: `buildPreOrder(0, 6, 0, 6)`

if (inStart > inEnd || postStart > postEnd) return;

0 > 6 또는 0 > 6 아니므로 → ❌조건 불만족 → 넘어감

int root = postorder[postEnd];

postorder[6] = 1 → 현재 서브트리의 루트는 1번 노드

sb.append(root).append(" ");

전위 순회는 루트를 먼저 출력하니까 → sb = "1 "

int rootIndex = indexInInorder[root];

indexInInorder[1] = 3 → 중위 순회에서 루트 1의 위치

int leftSize = rootIndex - inStart;  // 3 - 0 = 3

루트 왼쪽에 3개의 노드가 있다는 뜻

▶️ 왼쪽 서브트리 호출: `buildPreOrder(0, 2, 0, 2)`

🔁 2차 호출: `buildPreOrder(0, 2, 0, 2)`

postorder[2] = 2 → root`

sb = "1 2 "`

indexInInorder[2] = 1  
leftSize = 1

→ 왼쪽 재귀: `buildPreOrder(0, 0, 0, 0)`
→ 오른쪽 재귀: `buildPreOrder(2, 2, 1, 1)`

---

### 🔁 3차 호출: `buildPreOrder(0, 0, 0, 0)` → 왼쪽 자식 4

- `postorder[0] = 4 → root`
- `sb = "1 2 4 "`
- `indexInInorder[4] = 0`
- `leftSize = 0`

→ 왼쪽: `buildPreOrder(0, -1, 0, -1)` → 종료  
→ 오른쪽: `buildPreOrder(1, 0, 0, -1)` → 종료

⛔ 재귀 종료, 돌아감

---

### 🔁 4차 호출: `buildPreOrder(2, 2, 1, 1)` → 오른쪽 자식 5

- `postorder[1] = 5 → root`
- `sb = "1 2 4 5 "`
- `indexInInorder[5] = 2`
- `leftSize = 0`

→ 왼쪽: `buildPreOrder(2, 1, 1, 0)` → 종료  
→ 오른쪽: `buildPreOrder(3, 2, 1, 0)` → 종료

⛔ 재귀 종료, 돌아감

---

### 🔁 5차 호출: `buildPreOrder(4, 6, 3, 5)` → 오른쪽 트리로 진입

- `postorder[5] = 3 → root`
- `sb = "1 2 4 5 3 "`
- `indexInInorder[3] = 5`
- `leftSize = 1`

→ 왼쪽: `buildPreOrder(4, 4, 3, 3)`  
→ 오른쪽: `buildPreOrder(6, 6, 4, 4)`

---

### 🔁 6차 호출: `buildPreOrder(4, 4, 3, 3)` → 왼쪽 자식 6

- `postorder[3] = 6 → root`
- `sb = "1 2 4 5 3 6 "`
- `indexInInorder[6] = 4`
- `leftSize = 0`
→ 왼쪽/오른쪽 재귀 종료

---

### 🔁 7차 호출: `buildPreOrder(6, 6, 4, 4)` → 오른쪽 자식 7

- `postorder[4] = 7 → root`
- `sb = "1 2 4 5 3 6 7 "`
- `indexInInorder[7] = 6`
- `leftSize = 0`
→ 왼쪽/오른쪽 재귀 종료

---

## ✅ 최종 결과
출력값:

1 2 4 5 3 6 7


---

## 📌 전체 재귀 호출 구조 시각화

buildPreOrder(0,6,0,6) → root = 1
├─ buildPreOrder(0,2,0,2) → root = 2
│ ├─ buildPreOrder(0,0,0,0) → root = 4
│ └─ buildPreOrder(2,2,1,1) → root = 5
└─ buildPreOrder(4,6,3,5) → root = 3
├─ buildPreOrder(4,4,3,3) → root = 6
└─ buildPreOrder(6,6,4,4) → root = 7


---
아주 좋은 질문이에요!
`postStart` 값을 **재귀 함수 호출 시 어떻게 계산하는지** 이해하는 것은 이 문제에서 가장 어려운 부분 중 하나예요. 지금부터 **매우 천천히, 디버깅 방식으로**, **한 줄씩 흐름을 따라가며 설명**드릴게요.

---

## 🔁 메서드 시그니처 다시 확인:

```java
buildPreOrder(int inStart, int inEnd, int postStart, int postEnd)

이 메서드는 inorder[inStart ~ inEnd], postorder[postStart ~ postEnd] 구간을 가지고 재귀 호출해요.
그 중에서 postStart는 "현재 탐색하는 구간의 후위 순회 시작 위치"예요.

📥 예제 복습:

inorder    = [4, 2, 5, 1, 6, 3, 7]
postorder  = [4, 5, 2, 6, 7, 3, 1]

📌 1차 호출

buildPreOrder(0, 6, 0, 6)

현재 전체 트리 범위
루트는 postorder[6] = 1

루트의 중위 순회 위치 찾기:

root = 1
rootIndex = indexInInorder[1] = 3

→ 루트의 왼쪽에는 3개의 노드가 있으므로

leftSize = 3

✅ 왼쪽 서브트리 재귀 호출

buildPreOrder(
    inStart = 0,
    inEnd   = rootIndex - 1 = 2,
    postStart = 0,
    postEnd   = postStart + leftSize - 1 = 0 + 3 - 1 = 2
)

✔ 왼쪽 서브트리의 postStart는 지금 postStart 그대로 (0)
왜냐면 postorder는 "왼쪽 → 오른쪽 → 루트" 순서이기 때문에,
현재 postStart ~ postStart+leftSize-1 구간이 왼쪽 서브트리를 담당해요.

✅ 오른쪽 서브트리 재귀 호출

buildPreOrder(
    inStart = rootIndex + 1 = 4,
    inEnd   = 6,
    postStart = postStart + leftSize = 0 + 3 = 3,
    postEnd   = postEnd - 1 = 6 - 1 = 5
)

✔ 오른쪽 서브트리의 postStart는 현재 postStart + 왼쪽 서브트리 크기!
왜냐하면 왼쪽 서브트리가 postorder에서 먼저 나오고,
오른쪽 서브트리가 그 다음에 나오기 때문이에요.

📌 정리: postStart 계산 공식

어떤 서브트리	postStart 계산법	postEnd 계산법
왼쪽 서브트리	`postStart` 그대로	`postStart + leftSize - 1`
오른쪽 서브트리	`postStart + leftSize`	`postEnd - 1` (루트 제외)

📍 시각 예시 (예제: 1 2 4 5 3 6 7)

inorder:   [4, 2, 5, 1, 6, 3, 7]
index:       0  1  2  3  4  5  6

postorder: [4, 5, 2, 6, 7, 3, 1]
index:       0  1  2  3  4  5  6
                      ^        ^ 
                왼쪽 서브트리   루트 (1)

→ 왼쪽 트리의 postStart = 0, postEnd = 2  
→ 오른쪽 트리의 postStart = 3, postEnd = 5

🧠 요약

postStart는 후위 순회에서 어떤 서브트리를 처리할지 결정하는 기준입니다.
왼쪽 서브트리는 현재 postStart에서 시작, 크기는 leftSize
오른쪽 서브트리는 왼쪽 서브트리 뒤에서 시작 → postStart + leftSize

🧪 검증을 위한 한 번 더 디버깅 (재귀 2단계)

왼쪽 서브트리: buildPreOrder(0, 2, 0, 2)

루트 = postorder[2] = 2
indexInInorder[2] = 1, → leftSize = 1

왼쪽 자식 4

buildPreOrder(0, 0, 0, 0)  // postStart 그대로

오른쪽 자식 5

buildPreOrder(2, 2, 1, 1)  // postStart = postStart + leftSize = 0 + 1 = 1

모두 공식에 맞게 잘 들어맞죠!

🛠 결론

postStart는 현재 처리 중인 후위 순회 구간의 시작점
왼쪽/오른쪽 서브트리로 분할할 때 다음과 같이 갱신해요:

파라미터	왼쪽 서브트리	오른쪽 서브트리
postStart	`postStart`	`postStart + leftSize`
postEnd	`postStart + leftSize - 1`	`postEnd - 1`

류한선

good

이전 포스트

칸토어 집

다음 포스트

트리의 순회-7.13(대강 돌아가는 것만 봄)

실기연습-2

🧠 문제 개요 (요약)

🧪 예제 입력 (내가 정함)

✅ 전체 Java 코드

🔬 코드 한 줄씩 분석 + 예제 기반 흐름

(1) 입력 받기 부분

(2) 트리 재구성 및 전위 순회 출력 함수 호출

🌲 buildPreOrder 함수 상세 흐름 (재귀)

1차 호출: `buildPreOrder(0,6,0,6)`

왼쪽 트리 재귀: `buildPreOrder(0,2,0,2)`

왼쪽 자식: `buildPreOrder(0,0,0,0)` → root=4

오른쪽 자식: `buildPreOrder(2,2,1,1)` → root=5

오른쪽 트리 재귀: `buildPreOrder(4,6,3,5)`

왼쪽 자식: `buildPreOrder(4,4,3,3)` → root=6

오른쪽 자식: `buildPreOrder(6,6,4,4)` → root=7

✅ 최종 출력

📌 메서드 원형 다시 보기:

각 매개변수 의미:

📥 입력 예제 복습:

🔍 전체 흐름을 따라가며 디버깅

🔁 1차 호출: `buildPreOrder(0, 6, 0, 6)`

▶️ 왼쪽 서브트리 호출: `buildPreOrder(0, 2, 0, 2)`

🔁 2차 호출: `buildPreOrder(0, 2, 0, 2)`

📥 예제 복습:

📌 1차 호출

루트의 중위 순회 위치 찾기:

✅ 왼쪽 서브트리 재귀 호출

✅ 오른쪽 서브트리 재귀 호출

📌 정리: postStart 계산 공식

📍 시각 예시 (예제: 1 2 4 5 3 6 7)

🧠 요약

🧪 검증을 위한 한 번 더 디버깅 (재귀 2단계)

왼쪽 자식 4

오른쪽 자식 5

🛠 결론

칸토어 집

함정1

0개의 댓글

트리의 순회-7.13(대강 돌아가는 것만 봄)

실기연습-2

🧠 문제 개요 (요약)

🧪 예제 입력 (내가 정함)

✅ 전체 Java 코드

🔬 코드 한 줄씩 분석 + 예제 기반 흐름

(1) 입력 받기 부분

(2) 트리 재구성 및 전위 순회 출력 함수 호출

🌲 buildPreOrder 함수 상세 흐름 (재귀)

1차 호출: buildPreOrder(0,6,0,6)

왼쪽 트리 재귀: buildPreOrder(0,2,0,2)

왼쪽 자식: buildPreOrder(0,0,0,0) → root=4

오른쪽 자식: buildPreOrder(2,2,1,1) → root=5

오른쪽 트리 재귀: buildPreOrder(4,6,3,5)

왼쪽 자식: buildPreOrder(4,4,3,3) → root=6

오른쪽 자식: buildPreOrder(6,6,4,4) → root=7

✅ 최종 출력

📌 메서드 원형 다시 보기:

각 매개변수 의미:

📥 입력 예제 복습:

🔍 전체 흐름을 따라가며 디버깅

🔁 1차 호출: buildPreOrder(0, 6, 0, 6)

▶️ 왼쪽 서브트리 호출: buildPreOrder(0, 2, 0, 2)

🔁 2차 호출: buildPreOrder(0, 2, 0, 2)

📥 예제 복습:

📌 1차 호출

루트의 중위 순회 위치 찾기:

✅ 왼쪽 서브트리 재귀 호출

✅ 오른쪽 서브트리 재귀 호출

📌 정리: postStart 계산 공식

📍 시각 예시 (예제: 1 2 4 5 3 6 7)

🧠 요약

🧪 검증을 위한 한 번 더 디버깅 (재귀 2단계)

왼쪽 자식 4

오른쪽 자식 5

🛠 결론

칸토어 집

함정1

0개의 댓글

1차 호출: `buildPreOrder(0,6,0,6)`

왼쪽 트리 재귀: `buildPreOrder(0,2,0,2)`

왼쪽 자식: `buildPreOrder(0,0,0,0)` → root=4

오른쪽 자식: `buildPreOrder(2,2,1,1)` → root=5

오른쪽 트리 재귀: `buildPreOrder(4,6,3,5)`

왼쪽 자식: `buildPreOrder(4,4,3,3)` → root=6

오른쪽 자식: `buildPreOrder(6,6,4,4)` → root=7

🔁 1차 호출: `buildPreOrder(0, 6, 0, 6)`

▶️ 왼쪽 서브트리 호출: `buildPreOrder(0, 2, 0, 2)`

🔁 2차 호출: `buildPreOrder(0, 2, 0, 2)`