[백준/코틀린] 5639번: 이진 검색 트리

링크

5639번: 이진 검색 트리

풀이

Binary Search Tree

이진 검색 트리(BST)는 다음 성질을 가집니다.

• 왼쪽 서브트리의 모든 값은 루트보다 작다.
• 오른쪽 서브트리의 모든 값은 루트보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

이 성질을 이용해 원래의 이진 검색 트리를 복원할 수 있습니다.
트리를 구성한 뒤, 후위 순회(postorder)를 수행합니다.

코드

data class Node(
    val key: Int,
    var left: Node? = null,
    var right: Node? = null,
)

val ROOT = Node(0)

fun insert(node: Node?, key: Int) {
    node ?: return

    if (key < node.key) {
        if (node.left == null) node.left = Node(key)
        else insert(node.left, key)
    } else {
        if (node.right == null) node.right = Node(key)
        else insert(node.right, key)
    }
}

fun postorder(node: Node?) {
    node ?: return

    postorder(node.left)
    postorder(node.right)
    println(node.key)
}

fun main() {
    while (true) {
        try {
            insert(ROOT, readln().toInt())
        } catch (_: Exception) {
            return postorder(ROOT.right)
        }
    }
}