Minimum Depth of Binary Tree - LeetCode

Problem

1. input: 이진 트리의 루트 노드 root
2. output: 주어진 트리의 depth 리턴
   • The number of nodes in the tree is in the range [0, 105].
   • 1000 <= Node.val <= 1000

Idea

트리의 최소 depth를 구하는 문제로 BFS 탐색을 통해 처음 리프노드를 만났을 때, 해당 노드의 depth를 리턴하면 된다 → Sol1

Solution

1. BFS

   루트 노드를 시작으로 최초의 리프노드 찾기

   import java.util.*
   /**
    * Example:
    * var ti = TreeNode(5)
    * var v = ti.`val`
    * Definition for a binary tree node.
    * class TreeNode(var `val`: Int) {
    *     var left: TreeNode? = null
    *     var right: TreeNode? = null
    * }
    */
   class Solution {
       fun minDepth(root: TreeNode?): Int {
           if (root == null) return 0
           var depth = 10001
           val queue = LinkedList<Pair<TreeNode, Int>>()
           queue.offer(Pair(root!!, 1))
           while (queue.size > 0) {
               val start = queue.pollFirst()
               if (start.first!!.left == null && start.first!!.right == null) {
                   depth = minOf(depth, start.second)
                   return depth
               }
               if (start.first!!.left != null) queue.offerLast(Pair(start.first!!.left!!, start.second + 1))
               if (start.first!!.right != null) queue.offerLast(Pair(start.first!!.right!!, start.second + 1))
           }
           return depth
       }
   }
   

   시간 복잡도: 트리 탐색 = n

   

Point