Сложность: medium
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Пример:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.
👨💻 Алгоритм:
1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.
2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.
3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.
😎 Решение
class Solution {
private func solve(_ root: TreeNode?, _ parent: Int, _ gParent: Int) -> Int {
guard let root = root else {
return 0
}
return solve(root.left, root.val, parent)
+ solve(root.right, root.val, parent)
+ (gParent % 2 == 0 ? root.val : 0)
}
func sumEvenGrandparent(_ root: TreeNode?) -> Int {
return solve(root, -1, -1)
}
}Ставь 👍 и забирай 📚 Базу знаний