Условие

Дано бинарное дерево. Необходимо определить, является ли оно сбалансированным. Бинарное дерево сбалансировано, если для любого узла высота двух его поддеревьев отличается не более чем на 1.

Примеры

Input: root = [3, 9, 20, null, null, 15, 7] Output: true Explanation: Это дерево сбалансировано:

        3
       / \\
      9  20
         / \\
        15  7

Input: root = [1, 2, 2, 3, 3, null, null, 4, 4] Output: false Explanation: Это дерево несбалансировано:

           1
          / \\
         2   2
        / \\
       3   3
      / \\
     4   4

Решение

/**
 * 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 isBalanced(root: TreeNode?): Boolean {
    // Вспомогательная функция для вычисления высоты дерева
    // Если дерево не сбалансировано, возвращает -1
    fun height(node: TreeNode?): Int {
        if (node == null) return 0
        
        // Рекурсивный расчет высоты левого и правого поддеревьев
        val leftHeight = height(node.left)
        if (leftHeight == -1) return -1  // Если левое поддерево не сбалансировано

        val rightHeight = height(node.right)
        if (rightHeight == -1) return -1 // Если правое поддерево не сбалансировано

        // Проверка сбалансированности текущего узла
        if (abs(leftHeight - rightHeight) > 1) return -1

        // Возвращаем высоту текущего поддерева
        return max(leftHeight, rightHeight) + 1
    }

    // Если дерево сбалансировано, высота будет отличной от -1
    return height(root) != -1
}

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

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

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

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