Сложность: easy
Дано бинарное дерево, определите, является ли оно
сбалансированным по высоте.
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: true
👨💻 Алгоритм:
1️⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает: -1, если p является пустым поддеревом, т.е. null; 1 + max(height(p.left), height(p.right)) в противном случае.
2️⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы.
3️⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них: Если root == NULL, возвращаем true. Если abs(height(root.left) - height(root.right)) > 1, возвращаем false. В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).
😎 Решение:
class Solution:
def height(self, root: TreeNode) -> int:
if not root:
return -1
return 1 + max(self.height(root.left), self.height(root.right))
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
return (
abs(self.height(root.left) - self.height(root.right)) < 2
and self.isBalanced(root.left)
and self.isBalanced(root.right)
)
Ставь 👍 и забирай 📚 Базу знаний