Условие

Дано корневое дерево, где каждый узел может иметь несколько дочерних узлов. Требуется выполнить предобход (preorder traversal) по дереву и вернуть список значений узлов.

Примеры

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

Input: root = [1, null, 2, 3, 4, 5, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] Output: [1, 2, 3, 6, 7, 11, 14, 4, 8, 12, 5, 9, 13, 10]

Решение

/**
 * Definition for a Node.
 * class Node(var `val`: Int) {
 *     var children: List<Node?> = listOf()
 * }
 */
fun preorder(root: Node?): List<Int> {
    val result = mutableListOf<Int>()
    if (root == null) return result
    
    fun traverse(node: Node?) {
        if (node == null) return
        result.add(node.`val`) // Добавляем значение текущего узла
        node.children.forEach { traverse(it) } // Рекурсивно обходим дочерние узлы
    }
    
    traverse(root)
    return result
}

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

O(n), где n — количество узлов в дереве.

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

O(h), где h — высота дерева, для хранения стека вызовов.