[LeetCode] 111. MinimumDepthofBinaryTree. (해석, Kotlin 풀이)

문제

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

주어진 이진트리에서 트리의 최소 깊이를 구하여라.

최소 깊이는 루트 노드부터 가장 가까운 리프 노드까지 내려가는 최단 거리에 있는 노드의 수이다.

Note: 리프 노드는 자식 노드를 가지고 있지 않다.

풀이

1. BFS - 너비 우선 탐색

fun minDepth(root: TreeNode?): Int {
    if(root == null) return 0

    val q = ArrayDeque<TreeNode>()
    q.add(root)

    var depth = 1

    while (q.isNotEmpty()) {
        val curSize = q.size

        repeat(curSize) {
            val curNode = q.poll()
            if (curNode.left == null && curNode.right == null) return depth

            curNode.left?.let { q.add(it) }
            curNode.right?.let { q.add(it) }
        }

        depth++
    }

    return depth
}

BFS 구현할 때, 코틀린 언어의 특징을 이용해서 쉽게 구할 수 있었다.

 

큐가 비어있는지 확인하는 while문과 함께 repeat를 사용하면,

 

1. 동일한 깊이의 노드 수만큼 돌고(repeat)

2. depth를 증가시킨다음

3. 해당 repeat문동안 쌓인 큐의 사이즈만큼 다시 돌면서

 

계속해서 동일한 깊이의 노드 탐색을 repeat문 안에서 해결할 수 있다!

depth를 큐에 따로 저장하지 않아도 된다는 말!

 

 

시간 복잡도: O(n), 공간 복잡도: O(n)

https://github.com/jeongum/algorithm/blob/master/LT_111_MinimumDepthofBinaryTree.kt