백준 5639 이진 검색 트리

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

이진 검색 트리를 전위 순회한 결과가 주어지고, 이를 후위 순회한 결과를 출력하는 문제이다.

노드의 개수가 10,000개 이하이므로 전위 순회한 순서대로 직접 BST를 만들어 삽입하고, 순회하는 방법을 선택하기로 하였다.

입력으로 들어오는 것이 전위 순회의 결과이므로, 트리 구현에 필요한 함수는 삽입 함수와 순회 함수만 있으면 된다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val tree = BST()

    while(true){
        val num = readLine() ?: break
        tree.insert(num.toInt())
    }

    tree.print()
}

class BST{
    private var root: Node? = null

    fun insert(num: Int){
        if(root == null){
            root = Node(num)
        }else {
            insert(root, num)
        }
    }

    private fun insert(node: Node?, num: Int){
        when{
            node?.left != null && node.value > num -> insert(node.left, num)
            node?.right != null && node.value < num -> insert(node.right, num)
            node!!.left == null && node.value > num -> node.left = Node(num)
            node.right == null && node.value < num -> node.right = Node(num)
        }
    }

    fun print(){
        val sb = StringBuilder()
        print(root, sb)
        print(sb.toString())
    }

    private fun print(node: Node?, sb: StringBuilder){
        if(node == null) return

        print(node.left, sb)
        print(node.right, sb)
        sb.append("${node.value}\n")
    }
}

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

1. insert 함수는 root가 없으면 루트에, root가 있으면 재귀를 통해 값을 비교하여 빈 위치에 배치하도록 하였다.

2. print 함수는 노드의 개수가 최대 10,000개 이므로 속도를 위해 StringBuilder를 사용하였고, 후위 순회 순서대로 sb에 append한 후 한 번 출력하였다.