Balanced Binary Tree

Условие

Дано бинарное дерево. Необходимо определить, является ли оно сбалансированным. Бинарное дерево сбалансировано, если для любого узла высота двух его поддеревьев отличается не более чем на 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.