Сложность: 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 function solve($root, $parent, $gParent) {
if ($root === null) {
return 0;
}
return $this->solve($root->left, $root->val, $parent) + $this->solve($root->right, $root->val, $parent) + ($gParent % 2 == 0 ? $root->val : 0);
}
public function sumEvenGrandparent($root) {
return $this->solve($root, -1, -1);
}
}Ставь 👍 и забирай 📚 Базу знаний