BinarySearch 0903 Sum of Nodes with Even Grandparent Values

Problem statement

https://binarysearch.com/problems/Sum-of-Nodes-with-Even-Grandparent-Values/

Solution

Traverse tree, keeping parent and grandparent.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        def dfs(node, par, grand):
            if not node: return
            if grand != None and grand.val % 2 == 0:
                self.ans += node.val
            dfs(node.left, node, par)
            dfs(node.right, node, par)

        self.ans = 0
        dfs(root, None, None)
        return self.ans