[baekjoon] 백준 2263번 : 트리의 순회 (by python 파이썬) 재귀

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

2263번: 트리의 순회

정답 code

#트리의 순회
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

n = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))

#후위순회에서 최상위노드를 찾은후 중위순회에서 찾기위해 인덱스번호 부여
nodenum = [0] * (n+1)
for i in range(n):
    nodenum[inorder[i]] = i


def find_preorder(inorder_start,inorder_end,post_start,post_end):
    if (inorder_start>inorder_end) or (post_start>post_end):
        return

    root = postorder[post_end]
    #좌측 하위노드 = 최상위 노드의 인덱스 번호 - 중위순회 시작
    leftn = nodenum[root] - inorder_start
    #우측 하위노드 = 중위순회 마지막 - 최상위노드 인덱스번호
    rightn = inorder_end - nodenum[root]

    print(root, end = " ")
    #좌측
    find_preorder(inorder_start, inorder_start+leftn-1, post_start, post_start+leftn -1)
    #우측
    find_preorder( inorder_end-rightn+1, inorder_end, post_end - rightn, post_end-1)

find_preorder(0,n-1,0,n-1)

 

solution

 

용어설명

preorder  -  전위 순회

inorder - 중위 순회

postorder - 후위순회

 

중위 순회의 특징과 후위순위의 특징으로 전위순회를 구해야한다.

중위순회는 최상위 루트를 기준으로 왼쪽은 왼쪽 서브트리 오른쪽은 오른쪽 서브트리이다.

후위 순회는 마지막에 최상위 루트를 방문함으로 마지막이 최상위 루트가 된다.

 

따라서 

중위순회   7 3 8 1 9 4 10 0 11 5 2 6

후위 순회  7 8 3 9 10 4 1 11 5 6 2 0

 

위와 같은 입력을 받는다면 후위 순회 기준으로 제일 마지막 0이 최상위 루트가 되고,

이 0을 기준으로 중위순회에 대입하면,

7 3 8 1 9 4 10 이 왼쪽 서브트리  

11 5 2 6 이 오른쪽 서브트리가 된다.

 

대입하는 과정에서 중위 순위의 최상위루트의 인덱스를 알기위해 아래와 같이 중위순회에서의 인덱스 번호를 부여해준다.

nodenum = [0] * (n+1)
for i in range(n):
    nodenum[inorder[i]] = i

이러면 nodenum[후위순회에서 찾은 최상위루트] 를 찾으면 중위순회에서 해당수의 인덱스 번호를 알 수 있다.

ex) nodenum[0] = 7

왼쪽 서브트리 수  7-0 = 7

오른쪽 서브트리수  11(n-1) -7 = 4

 

이걸통해 중위 순회와 후위순회에 왼쪽 서브트리와 오른쪽 서브트리의 범위를 구할 수 있다.

중위순회 기준

왼쪽 서브트리 - (시작 인덱스  ~~ 시작 인덱스 + 왼쪽 서브트리 갯수 - 1)  ex) 0~6

오른쪽 서브트리  - (끝 인덱스 - 오른쪽 서브트리 갯수  + 1  ~~  끝 인덱스) ex) 8~11  

** 중간에 최상위 루트 제외

 

후위순회 기준 

왼쪽 서브트리 - (시작 인덱스  ~~ 시작 인덱스 + 왼쪽 서브트리 갯수 - 1)  ex) 0~6

오른쪽 서브트리  - (끝 인덱스 - 오른쪽 서브트리 갯수   ~~  끝 인덱스 - 1) ex) 7~10

** 맨끝에 최상위 루트 제외

 

이와 같은 방법을 재귀해가며 찾으면된다.

1. 입력된 후위순회에서 제일끝 값 저장후 출력 (최상위 루트) 

2. 저장한 값(최상위루트)로 중위순회에서 해당 인덱스를 찾은후 왼쪽과 오른쪽 갯수 저장

3. 왼쪽과 오른쪽 서브트리 저장값을 이용해 재귀를 이어나감

4. 재귀된 함수 내에서 1~3 반복

 

 

런타임 에러 (RecursionError)

** 재귀의 한도를 늘려주는것 잊지 말자!! 

sys.setrecursionlimit(10**7)