← Static tasks

1315. Sum of Nodes with Even-Valued Grandparent

leetcode medium

#csharp#leetcode#medium#recursion#tree#two-pointers

Task

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.

C# solution

matched/original
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);
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    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);
    }
}

Java solution

matched/original
class Solution {
    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 ? 0 : root.val);
    }

    public int sumEvenGrandparent(TreeNode root) {
        return solve(root, -1, -1);
    }
}

Python solution

matched/original
class Solution:
    def solve(self, root: TreeNode, parent: int, gParent: int) -> int:
        if not root:
            return 0
        return self.solve(root.left, root.val, parent) + self.solve(root.right, root.val, parent) + (root.val if gParent % 2 == 0 else 0)

    def sumEvenGrandparent(self, root: TreeNode) -> int:
        return self.solve(root, -1, -1)

Go solution

matched/original
func solve(root *TreeNode, parent, gParent int) int {
    if root == nil {
        return 0
    }
    return solve(root.Left, root.Val, parent) + solve(root.Right, root.Val, parent) + func() int {
        if gParent%2 == 0 {
            return root.Val
        }
        return 0
    }()
}

func sumEvenGrandparent(root *TreeNode) int {
    return solve(root, -1, -1)
}

Explanation

Algorithm

Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.

Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.

Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.

😎