Sum of Nodes with Even-Valued Grandparent

Problem Id: 1315 Difficulty: Medium Tag: Tree Tag: Depth-first Search


Intuition

A general kind of solution in DFS problems is to pass an additional variable parent. In this case, we need to pass one more variable grandparent when doing the DFS process.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        self.even_sum = 0
        self._dfs(root, None, None)
        return self.even_sum

    def _dfs(self, node, parent, grandparent):
        if node is None:
            return
        if grandparent and grandparent.val % 2 == 0:
            self.even_sum += node.val
        self._dfs(node.left, node, parent)
        self._dfs(node.right, node, parent)