// Временная сложность: O(n²) - для каждого узла вычисляем глубину, что требует обхода поддерева// Пространственная сложность: O(h) - глубина рекурсии, где h - высота дерева (в худшем случае O(n))var isBalanced = function(root) { if (!root) return true; const getDepth = (node) => { if (!node) return 0; return 1 + Math.max(getDepth(node.left), getDepth(node.right)); } // 1. Корень сбалансирован? const rootBalanced = Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1; // 2. И левое поддерево сбалансировано? И правое тоже? return rootBalanced && isBalanced(root.left) && isBalanced(root.right);};
Решение 2
// Временная сложность: O(n) — каждый узел посещаем один раз. // Пространственная сложность: O(h) — стек рекурсии (h = высота дерева; худший случай O(n), если дерево вырождено).var isBalanced = function(root) { // Функция возвращает высоту, если сбалансировано, или -1, если нет function checkHeight(node) { if (!node) return 0; const leftH = checkHeight(node.left); if (leftH === -1) return -1; // Уже нашли ошибку слева const rightH = checkHeight(node.right); if (rightH === -1) return -1; // Уже нашли ошибку справа // Сама проверка баланса if (Math.abs(leftH - rightH) > 1) return -1; // Возвращаем реальную высоту return 1 + Math.max(leftH, rightH); } return checkHeight(root) !== -1;};