Binary Tree Inorder Traversal

Условие

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

Примеры

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

Output: [1, 3, 2]

Explanation: Inorder traversal: посещаем левый узел (пусто), корневой узел (1), правый узел (сначала левый узел 3, потом корневой 2). Дерево выглядит так:

    1
     \
      2
     /
    3

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

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

Explanation:

      1
   /     \
  2       3
 / \       \
4   5       8
   / \     /
  6   7   9

Input: root = []

Output: []

Explanation: Пустое дерево.

Input: root = [1]

Output: [1]

Explanation: Дерево с одним узлом.

Решение

/**
 * 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 inorderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    
    // Вспомогательная функция для рекурсивного обхода
    fun traverse(node: TreeNode?) {
        if (node == null) return
        
        // Сначала обходим левое поддерево
        traverse(node.left)
        
        // Посещаем корневой узел
        result.add(node.`val`)
        
        // Затем обходим правое поддерево
        traverse(node.right)
    }
    
    // Запускаем рекурсивный обход с корня
    traverse(root)
    
    return result
}

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

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

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

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