Binary Tree Paths

Условие

Дано двоичное дерево, верните все пути от корня до листьев в виде строк.

Примеры

Input: root = [1, 2, 3, null, 5]

Output: ["1 → 2 → 5", "1 → 3"]

Input: root = [1]

Output: ["1"]

Решение

/**
 * 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 binaryTreePaths(root: TreeNode?): List<String> {
    val paths = mutableListOf<String>() // Список для хранения всех путей
    
    fun constructPaths(node: TreeNode?, path: String) {
        if (node != null) { // Проверяем, не пустой ли узел
            // Формируем новый путь, добавляя значение текущего узла
            val newPath = if (path.isEmpty()) node.`val`.toString() else "$path->${node.`val`}"
            
            // Проверяем, является ли текущий узел листом (не имеет детей)
            if (node.left == null && node.right == null) {
                paths.add(newPath) // Если лист, добавляем путь в список
            } else {
                // Рекурсивно вызываем для левого поддерева
                constructPaths(node.left, newPath)
                // Рекурсивно вызываем для правого поддерева
                constructPaths(node.right, newPath)
            }
        }
    }
    
    constructPaths(root, "") // Начинаем с корня и пустого пути
    
    return paths // Возвращаем список всех найденных путей
}

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

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

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

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