Sum of Nodes with Even-Valued Grandparent

Although labeled as Medium, the problem is actually quite easy: https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/

1315. Sum of Nodes with Even-Valued Grandparent
Medium
Given a binary tree, return the sum of values of nodes with even-valued grandparent.  (A grandparent of a node is the parent of its parent, if it exists.)
If there are no nodes with an even-valued grandparent, return 0.

Example 1:
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.

Constraints:
  • The number of nodes in the tree is between 1 and 10^4.
  • The value of nodes is between 1 and 100.
Accepted
2,014
Submissions
2,439

Approach:
 - DFS PreOrder
 - Carry over parent value and grandparent value
 - Simple base case to add to the sum
 - Induction changing the parent and grandparent accordingly

Code is below, cheers, ACC.


public class Solution
{
    public int SumEvenGrandparent(TreeNode root)
    {
        int sum = 0;
        SumEvenGrandparent(root, -1, -1, ref sum);
        return sum;
    }

    private void SumEvenGrandparent(TreeNode node,
                                    int parent,
                                    int grandparent,
                                    ref int sum)
    {
        if (node == null) return;
        if (grandparent % 2 == 0) sum += node.val;
        SumEvenGrandparent(node.left, node.val, parent, ref sum);
        SumEvenGrandparent(node.right, node.val, parent, ref sum);
    }
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons