백준 2263 트리의 순회
23 Jun 2021https://www.acmicpc.net/problem/2263
순회는 모든 노드를 한번씩 방문하는 방법을 이야기한다. 이진트리에서는 preorder, inorder, postorder 3가지의 순회 방법이 존재한다. 그 중에서 이 문제는 인오더와 포스트오더가 주어졌을 때 프리오더를 구하는 문제이다.
1. preorder (전위 순회) : (루트)(왼쪽 자식)(오른쪽 자식)
2. inorder (중위 순회) : (왼쪽 자식)(루트)(오른쪽 자식)
3. postorder (후위 순회) : (왼쪽 자식)(오른쪽 자식)(루트)
방법은 간단하다. 포스트에서 맨 마지막이 루트를 나타날 것이기 때문에 해당 값으로 인오더에서 루트의 위치를 찾아준 다음에 그 정보를 활용하여 inorder와 postorder를 왼쪽 자식과 오른쪽 자식으로 구분짓는다. 루트는 preorder list에 추가시켜주고 왼쪽 자식, 오른쪽 자식 각각에 대해 재귀적으로 루트를 찾는 과정을 반복하면 preorder를 완성할 수 있다.
유의할 것은 inorder와 postorder가 처음에는 start index와 end index가 동일하지만 진행하면서 달라진다는 점이다. 따라서 왼쪽 자식과 오른쪽 자식을 나눌 때 둘의 index 범위가 다르다는 것을 유의하고 진행해야 한다.
- 전체 코드
let n = Int(readLine()!)!
let inorder = readLine()!.split(separator: " ").map{Int(String($0))!}
let postorder = readLine()!.split(separator: " ").map{Int(String($0))!}
var preorder:[String] = []
var inorderDic:[Int:Int] = [:]
inorder.enumerated().forEach {
inorderDic[$0.element] = $0.offset
}
func orderChange(inorderS: Int, inorderE: Int, postorderS: Int, postorderE: Int) {
if inorderS > inorderE {
return
}
else {
let rootNode = postorder[postorderE]
let rootIndex = inorderDic[rootNode]!
let postLeftEnd = rootIndex - inorderS + postorderS - 1
preorder.append(String(rootNode))
orderChange(inorderS: inorderS, inorderE: rootIndex-1, postorderS: postorderS, postorderE: postLeftEnd)
orderChange(inorderS: rootIndex+1, inorderE: inorderE, postorderS: postLeftEnd+1, postorderE: postorderE-1)
}
}
orderChange(inorderS: 0, inorderE: n-1, postorderS: 0, postorderE: n-1)
print(preorder.joined(separator: " "))