Binary Tree Preorder Traversal

https://leetcode.com/problems/binary-tree-preorder-traversalEasy

Условие

Дано бинарное дерево, нужно вернуть его прямой (preorder) обход. Прямой обход дерева подразумевает посещение узлов в следующем порядке:

  1. Корень.
  1. Левое поддерево.
  1. Правое поддерево.

Примеры

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

Output: [1, 2, 3]

Explanation: Корень дерева — 1, правый потомок — 2, левый потомок 2 — 3.
Input: root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]

Output: [1, 2, 4, 5, 6, 7, 3, 8, 9]
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 preorderTraversal(root: TreeNode?): List<Int> {
    // Список для хранения результатов
    val result = mutableListOf<Int>()
    
    // Рекурсивная функция для обхода дерева
    fun traverse(node: TreeNode?) {
        if (node == null) return // Базовый случай: если узел пуст, выходим
        
        result.add(node.`val`) // 1. Посещаем корень
        traverse(node.left)    // 2. Рекурсивно обходим левое поддерево
        traverse(node.right)   // 3. Рекурсивно обходим правое поддерево
    }
    
    traverse(root) // Запуск обхода дерева с корня
    return result  // Возвращаем список с результатами
}

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

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

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

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