[BOJ 4256] 트리 C++/Kotlin

 

4256번: 트리

 

 

문제풀이

 

처음에 문제를 읽고 어떻게 해야될지 한참 생각해도 잘 모르겠어서 다른 블로그 글을 참고했다.

[백준 4256] 트리

 

 

 

위 트리를 살펴보자.

 

전위 순회 : 3 6 5 4 8 7 1 2

중위 순회 : 5 6 8 4 3 1 2 7

후위 순회 : 5 8 4 6 2 1 7 3

 

전위 순회(preorder)는 루트부터 시작하고, 중위 순회(inorder)는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다.

전위 순회의 첫번째가 3이므로 중위 순회에서 루트 노드를 찾아서 왼쪽, 오른쪽 트리의 노드 개수를 구할 수 있다.

루트 노드는 3이고 5 6 8 4는 왼쪽 서브트리, 1 2 7은 오른쪽 서브트리이다.

 

전위 순회에서 루트 노드 바로 다음 값이 루트 노드의 왼쪽 자식이고 왼쪽 트리의 노드 수만큼 더하면 오른쪽 자식이다.

양 서브트리의 루트(최상단) 노드는 전위 순회의 첫번째 노드이므로 각각 6, 7이다.

루트 노드를 찾았으면 또 이등분하여 서브트리를 구한다.

 

 

코드

 

C++ 코드

 

 

Kotlin 코드

 

• 계속 NumberFormatException이 났는데 입력 받을 때 trim()을 해주니까 해결됨