파이썬, SWEA 1231, 중위 순회

---

난이도 : D4

링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD

---

1. 문제 설명

설명

주어진 트리를 in-order 형식으로 순회해 각 노드를 읽으면 특정 단어를 알 수 있다.

 
위 트리를 in-order 형식으로 순회할 경우 SOFTWARE 라는 단어를 읽을 수 있다.
주어진 트리를 in-order 형식으로 순회했을때 나오는 단어를 출력하라.

[제약 사항]

트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 문자만 저장할 수 있다.

노드는 아래 그림과 같은 순서로 주어진다.
 

---

입력

총 10개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 트리가 갖는 정점의 총 수 N(1≤N≤100)이 주어진다. 그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다.

정점 정보는 해당 정점의 문자, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점 번호 순서로 주어진다.

정점 번호는 1부터 N까지의 정수로 구분된다. 정점 번호를 매기는 규칙은 위 와 같으며, 루트 정점의 번호는 항상 1이다.

위의 예시에서,  알파벳 ‘F’가 2번 정점에 해당하고 두 자식이 각각 알파벳 ‘O’인 4번 정점과 알파벳 ‘T’인 5번 정점이므로 “2 F 4 5”로 주어진다.
알파벳 S는 8번 정점에 해당하므로 “8 S” 로 주어진다.

---

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 답을 출력한다.

---

---

2. 문제리뷰

재귀를 사용하려면..

• 문제의 정의를 정확히 표기한다.
• 종료조건을 정확히 표기한다.
• 컬스택-호출의 흐름을 따라갈 줄 알아야 한다.

01. 문제의 정의

- 주어진 tree를 in-order 형식으로 순회

02. 종료조건

- now > n

03. 컬스택-호출 흐름

ex)

8
1 W 2 3
2 F 4 5
3 R 6 7
4 O 8
5 T
6 A
7 E
8 S

8 - 4 - 2 - 5 - 1 - 6 - 7 -3

---

3. 소스코드

def inorder(now):
    if now > n:
        return
    inorder(now * 2)
    print(tree[now], end='')
    inorder(now * 2 + 1)

for tc in range(1, 11):
    n = int(input())
    tree = [0] * (n+1)
    for i in range(1, n+1):
        arr = list(input().split())
        tree[i] = arr[1]
    print(f'#{tc}', end=' ')
    inorder(1)
    print()