Условие

Дано корневое дерево, выполните постобход и верните значения узлов в порядке обхода.

Примеры

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

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: [2, 6, 14, 11, 7, 3, 4, 8, 9, 10, 12, 13, 5, 1]

Решение

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

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

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

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

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