Сложность: 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. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.
😎 Решение:
public class Solution {
private int Solve(TreeNode root, int parent, int gParent) {
if (root == null) {
return 0;
}
return Solve(root.left, root.val, parent) + Solve(root.right, root.val, parent) + (gParent % 2 == 0 ? root.val : 0);
}
public int SumEvenGrandparent(TreeNode root) {
return Solve(root, -1, -1);
}
}Ставь 👍 и забирай 📚 Базу знаний