Условие

Дано бинарное дерево. Наклон (tilt) узла дерева определяется как абсолютная разница между суммой значений всех узлов левого поддерева и суммой значений всех узлов правого поддерева. Наклон всего дерева — это сумма наклонов всех его узлов.

Необходимо вернуть наклон всего дерева.

Примеры

Input: root = [1, 2, 3] Output: 1 Explanation:

Наклон узла со значением 2 равен 0. Наклон узла со значением 3 равен 0. Наклон узла со значением 1 равен |2 - 3| = 1. Общий наклон дерева равен 1.

Input: root = [4, 2, 9, 3, 5, null, 7] Output: 15 Explanation:

Наклон узла со значением 3 равен 0. Наклон узла со значением 5 равен 0. Наклон узла со значением 7 равен 0. Наклон узла со значением 2 равен |3 - 5| = 2. Наклон узла со значением 9 равен |7 - 0| = 7. Наклон узла со значением 4 равен |10 - 16| = 6. Общий наклон дерева равен 15.

Input: root = [21, 7, 14, 1, 1, 2, 2, 3, 3] Output: 9

Решение

/**
 * 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 findTilt(root: TreeNode?): Int {
    var totalTilt = 0

    // Вспомогательная функция для вычисления суммы поддерева и обновления наклона
    fun subtreeSum(node: TreeNode?): Int {
        if (node == null) return 0

        // Вычисляем суммы левого и правого поддеревьев
        val leftSum = subtreeSum(node.left)
        val rightSum = subtreeSum(node.right)

        // Обновляем общий наклон дерева
        totalTilt += kotlin.math.abs(leftSum - rightSum)

        // Возвращаем сумму текущего узла
        return leftSum + rightSum + node.`val`
    }

    // Запускаем рекурсивную функцию для корневого узла
    subtreeSum(root)

    return totalTilt
}

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

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

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

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