[백준/코틀린] 1991번: 트리 순회

링크

1991번: 트리 순회

풀이

각 노드의 왼쪽 자식과 오른쪽 자식이 주어지는 이진 트리를 입력받아,
루트 노드(A)를 기준으로 전위 순회, 중위 순회, 후위 순회 결과를 각각 구합니다.

재귀적으로 구현한 DFS로 트리를 탐색하며,
각 순회 방식에 맞춰 노드의 값을 기록합니다.

• 전위(preorder): 루트 → 왼쪽 자식 → 오른쪽 자식
• 중위(inorder): 왼쪽 자식 → 루트 → 오른쪽 자식
• 후위(postorder): 왼쪽 자식 → 오른쪽 자식 → 루트

코드

data class Node(
    val left: Char,
    val right: Char,
)

val tree = HashMap<Char, Node>()
val preorder = StringBuilder()
val inorder = StringBuilder()
val postorder = StringBuilder()

fun dfs(value: Char) {
    val node = tree[value] ?: return

    preorder.append(value)
    dfs(node.left)
    inorder.append(value)
    dfs(node.right)
    postorder.append(value)
}

fun main() {
    repeat(readln().toInt()) {
        val (value, left, right) = readln().split(" ").map { it[0] }

        tree[value] = Node(left, right)
    }
    dfs('A')

    println(preorder.toString())
    println(inorder.toString())
    println(postorder.toString())
}