Условие

Дано бинарное дерево, нужно найти его минимальную глубину. Минимальная глубина — это количество узлов от корня до ближайшего листа (узел без детей). Обратите внимание, что путь должен заканчиваться на листе, а не просто на пустом узле.

Примеры

Input: root = [3, 9, 20, null, null, 15, 7] Output: 2 Explanation: Минимальная глубина равна 2, потому что ближайший лист находится на втором уровне:

        3
       / \\
      9  20
         / \\
        15  7

Input: root = [2,null,3,null,4,null,5,null,6] Output: 5 Explanation: Минимальная глубина равна 5, потому что единственный путь до листа состоит из 5 узлов:

     2
      \\
       3
        \\
         4
          \\
           5
            \\
             6

Решение

/**
 * 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
 * }
 */
fun minDepth(root: TreeNode?): Int {
    // Если дерево пустое, глубина равна 0
    if (root == null) return 0
    
    // Если у узла нет левого поддерева, рекурсивно идем вправо
    if (root.left == null) return minDepth(root.right) + 1
    
    // Если у узла нет правого поддерева, рекурсивно идем влево
    if (root.right == null) return minDepth(root.left) + 1
    
    // Если есть оба поддерева, ищем минимальную глубину среди них
    return min(minDepth(root.left), minDepth(root.right)) + 1
}

Временная сложность

O(n), где n — количество узлов в дереве. Мы посещаем каждый узел один раз для расчета минимальной глубины.

Пространственная сложность

O(h), где h — высота дерева. Это максимальная глубина рекурсивного стека, в худшем случае она может быть равна количеству узлов в дереве.