1315.Sum of Nodes with Even-Valued Grandparent

In [4]:

from binarytree import Node, build
from collections import deque

Sum of Nodes with Even-Valued Grandparent

leetcode

Tip: we can use nonlocal ans declared in dfs function instead of using self.ans.

In [6]:

class Solution:
    def __init__(self):
        self.ans = 0
    def sumEvenGrandparent(self, root: Node) -> int:
        # root.pprint()
        def dfs(cur: Node, pars:list):
            # nonlocal ans
            if not cur:
                return
            gpv = -1
            if len(pars) == 2:
                gpv = pars[0]
                pars.pop(0)
            dfs(cur.left, pars + [cur.value])
            dfs(cur.right, pars + [cur.value])
            if gpv % 2 == 0:
                self.ans += cur.value
                # ans += cur.value
        dfs(root, [])
        return self.ans

sol = Solution()

In [8]:

null = None
A = [6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]
root = build(A)
root.pprint()

      ______6__
     /         \
    7__         8
   /   \       / \
  2     7     1   3
 /     / \         \
9     1   4         5

In [9]:

print(sol.sumEvenGrandparent(root))

18

Submitted Code

In [2]:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def __init__(self):
        self.ans= 0
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        # root.pprint()
        def dfs(cur: TreeNode, pars:list):
            if not cur:
                return
            gpv = -1
            if len(pars) == 2:
                gpv = pars[0]
                pars.pop(0)
            dfs(cur.left, pars + [cur.val])
            dfs(cur.right, pars + [cur.val])
            if gpv % 2 == 0:
                self.ans += cur.val
        dfs(root, [])
        return self.ans

Discuss

I cited a code in the document.

In [16]:

class Solution:
    def sumEvenGrandparent(self, root: Node) -> int:
        def dfs(cur: Node, par: Node, gpar: Node):
            if not cur:
                return
            nonlocal ans
            # ans value in updated in the inorder.
            if par and gpar and gpar.value % 2 == 0:  
                ans += cur.value
            dfs(cur.left, cur, par)
            dfs(cur.right, cur, par)

        ans = 0
        dfs(root, None, None)
        return ans
    
sol = Solution()

In [17]:

null = None
A = [6, 7, 8, 2, 7, 1, 3, 9, null, 1, 4, null, null, null, 5]
root = build(A)
root.pprint()
print(sol.sumEvenGrandparent(root))

      ______6__
     /         \
    7__         8
   /   \       / \
  2     7     1   3
 /     / \         \
9     1   4         5

18