Сложность: 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 TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
self.val = val
self.left = left
self.right = right
}
}
class Solution {
func height(_ root: TreeNode?) -> Int {
guard let root = root else {
return -1
}
return 1 + max(height(root.left), height(root.right))
}
func isBalanced(_ root: TreeNode?) -> Bool {
guard let root = root else {
return true
}
return abs(height(root.left) - height(root.right)) < 2 &&
isBalanced(root.left) && isBalanced(root.right)
}
}Ставь 👍 и забирай 📚 Базу знаний