[백준(BOJ)] #2263- 트리의 순회 (파이썬, Python3)

문제

 

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

2263번: 트리의 순회

 

---

문제 풀이

 

 이 문제를 풀 때 생각보다 방법이 쉽게 생각나서 빨리 풀겠다 생각했는데 구현에서 애먹어서 성공까지 가는데 오래 걸렸네요..ㅋㅋㅋㅋㅋㅋ 방법 자체는 트리 순회의 특징과 재귀 호출에 대해 어느 정도 알고 있으면 그렇게 어렵지는 않습니다!

 

트리 --> 2022.07.08 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 트리(Tree)

[파이썬으로 배우는 자료구조] 트리(Tree)

재귀 알고리즘 --> 2022.07.05 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

[파이썬으로 배우는 알고리즘] 재귀(Recursion) 알고리즘

 

1) 후위순회에서 마지막에 오는 값은 트리의 루트
2) 중위순회에서 루트를 기준으로 왼쪽 서브 트리와 오른쪽 서브 트리를 나눌 수 있음
3) 후위순회를 중위순회와 같이 나눈 후 각 서브 트리에서 마지막에 오는 값은 서브 트리의 루트
4) 위와 같은 성질을 이용해 재귀적으로 루트를 구해서 풀면 됨

 

풀이 과정

1) 후위순회의 마지막 값은 루트 노드로 중위순회에서 마지막 값인 1이 있는 자리를 찾음

 

2) 중위순회에서 1을 기준으로 왼쪽은 왼쪽 서브 트리이고, 오른쪽은 오른쪽 서브 트리를 구성

 

3) 루트 노드 처리 후 중위순회에서의 루트 노드의 자리를 기준으로 후위순회도 나눠줌. 후위순회에서 나눠진 서브 트리의 마지막 값은 마찬가지로 서브 트리의 루트 노드가 됨. 이 성질을 이용하여 왼쪽에서 오른쪽 순으로 재귀 호출!

 

왼쪽 서브 트리 재귀

 

오른쪽 서브 트리 재귀

---

구현

코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def preorder(inorder_s, inorder_e, postorder_s, postorder_e):
    # 재귀함수 종료 조건
    if (inorder_s > inorder_e) or (postorder_s > postorder_e):
        return
    
    # 후위 순회의 마지막 노드 출력
    p = postorder[postorder_e]
    print(p, end =' ')
    
    # 후위 순회의 마지막 값이 중위 순회에 어디에 위치 하는지 구했던 리스트가 여기서 사용
    left = inorder_pos[p] - inorder_s
    right = inorder_e - inorder_pos[p]
    
    # 왼쪽 서브 트리
    preorder(inorder_s, inorder_s+left-1, postorder_s, postorder_s+left-1)
    # 오른쪽 서브 트리
    preorder(inorder_e - right + 1, inorder_e, postorder_e - right, postorder_e - 1)

if __name__ == "__main__":
    n = int(input())
    inorder = list(map(int, input().split()))
    postorder = list(map(int, input().split()))
    inorder_pos = [0] * (n+1)
    
    # 후위순회의 마지막값이 중위순회 몇번째에 존재하는지 알기 위해 사용. 범위를 나누는 기준!
    for i in range(n):
        inorder_pos[inorder[i]] = i
        
    preorder(0, n-1, 0, n-1)

 

결과