Sum of Left Leaves

Условие

Дано бинарное дерево, нужно найти сумму всех левых листьев. Лист — это узел без дочерних узлов, а левый лист — это лист, который является левым дочерним узлом своего родителя.

Примеры

Input: root = [3, 9, 20, null, null, 15, 7]

Output: 24

Explanation: Левый лист только один — узел 9.

Input: root = [1]

Output: 0

Решение

/**
 * 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 sumOfLeftLeaves(root: TreeNode?): Int {
    if (root == null) return 0  // Если корень пуст, возвращаем 0

    var sum = 0

    // Если левый дочерний узел — лист, добавляем его значение к сумме
    if (root.left != null && root.left?.left == null && root.left?.right == null) {
        sum += root.left!!.`val`
    }

    // Рекурсивно вычисляем сумму для левого и правого поддеревьев
    sum += sumOfLeftLeaves(root.left)
    sum += sumOfLeftLeaves(root.right)

    return sum
}

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

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

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

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