Сложность: medium
Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем.
Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь.
Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию.
Пример:
Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
👨💻 Алгоритм:
1⃣ Инициализация и базовый случай:
Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел.
Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0].
2⃣ Рекурсивное исследование дерева:
В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла.
Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся.
Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка.
3⃣ Возврат результата:
В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper.
😎 Решение:
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil }
}
class Solution {
func rob(_ root: TreeNode?) -> Int {
let answer = helper(root)
return max(answer[0], answer[1])
}
func helper(_ node: TreeNode?) -> [Int] {
if node == nil {
return [0, 0]
}
let left = helper(node?.left)
let right = helper(node?.right)
let rob = node!.val + left[1] + right[1]
let notRob = max(left[0], left[1]) + max(right[0], right[1])
return [rob, notRob]
}
}Ставь 👍 и забирай 📚 Базу знаний