ゼロから始めるLeetCode Day11 「1315. Sum of Nodes with Even-Valued Grandparent」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day10 「1431. Kids With the Greatest Number of Candies」
次回
ゼロから始めるLeetCode Day12 「617. Merge Two Binary Trees」

問題

1315. Sum of Nodes with Even-Valued Grandparent

難易度はMediumです。

二分木が与えられ、その親の親、つまり祖父母の値が偶数であるノードの合計値を返すようにすればよいですね。
なお存在しない場合は0を返すようにします。

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.

例はこのようになっており、祖父母でありかつ偶数であるという条件に該当するのが6と8、そして6の孫にあたるのが[2,7,1,3]、8の孫にあたる[5]の合計値である18が返されています。

解法

問題をみたときに思いついたのは、現在のノード、親ノード、そして祖父母ノードをスライドさせながら保持し、仮に祖父母ノードが存在し、かつその値を2で割った時の余りが0であるならば現在のノードを合計値に加算する、という考え方です。
この考え方を実装した物が以下のものです。

# 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:
    ans = 0
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(cur:TreeNode,par:TreeNode,gra:TreeNode):
            if gra and gra.val % 2 == 0:
                self.ans += cur.val
            if cur.left:
                dfs(cur.left,cur,par)
            if cur.right:
                dfs(cur.right,cur,par)

        dfs(root,None,None)
        return self.ans
# Runtime: 92 ms, faster than 98.47% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.

今回は考え方が効率が良かったようで非常にシンプルにかけました。速さも十分ですし、なかなかに良い答えが出たと思います。

ansの位置が気になる人がいるかもしれませんが、Pythonでは関数の中で途中まではグローバル変数を参照し、途中からローカル変数に定義しなおすことはできず、関数のどこかでローカル変数として定義した変数は関数に入った時点で最初からローカル変数として扱われます。なのでこのような形になっています。

なんか気持ち悪かったので色々調べてみると、Pythonにはnonlocal変数なるものがあることを知りました。
関数内に関数を定義する際に、内側の関数から外側の関数内の変数を変更するために使うようで、使って書くとこう書けます。

# 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 sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(cur:TreeNode,par:TreeNode,gra:TreeNode):
            if gra and gra.val % 2 == 0:
                nonlocal ans
                ans += cur.val
            if cur.left:
                dfs(cur.left,cur,par)
            if cur.right:
                dfs(cur.right,cur,par)
        ans = 0
        dfs(root,None,None)
        return ans
# Runtime: 92 ms, faster than 98.47% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.

速さも変わらないし、こっちの方がスッキリしていて個人的には好きかもしれないです。