Binary Tree Postorder Traversal

Условие

Дано бинарное дерево, нужно вернуть список значений его вершин в порядке обхода postorder (левое поддерево -> правое поддерево -> корень).

Примеры

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

Output: [3, 2, 1]

Explanation: Сначала посещаем левое поддерево (null), затем правое поддерево (сначала 3, затем 2), потом корень (1).

Input: root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]

Output: [4, 6, 7, 5, 2, 9, 8, 3, 1]

Input: root = []

Output: []

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 postorderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    
    fun traverse(node: TreeNode?) {
        if (node == null) return
        
        // Сначала обходим левое поддерево
        traverse(node.left)
        // Затем правое поддерево
        traverse(node.right)
        // И наконец, добавляем значение корня
        result.add(node.`val`)
    }
    
    traverse(root)
    return result
}

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

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

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

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