ゼロから始めるLeetCode Day8 「1302. Deepest Leaves Sum」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day7 「104. Maximum Depth of Binary Tree」
次回
ゼロから始めるLeetCode Day8 「1302. Deepest Leaves Sum」

問題

1302. Deepest Leaves Sum

初のMediumです。
今回の問題もgoodの数が多く、いい問題だと思ったので解いてみました。

問題は至って簡単で、二分木が与えられるので最も深い葉の合計値を返してくれってことですね。最近木関連の問題が多い気がする・・・
なお、例は以下の通り
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15

この場合は最も深い葉が7と8なので足して15、ということですね。

問題をパッとみた感じでは深さ優先探索で一通り全ての葉の深さを調べて深さと値を返す、というのが簡単な考え方かなぁと思いました。
ただ、それでは少し冗長なコードになってしまう気がしましたし、深さを調べるときに同時にハッシュテーブルを使えば深さと値を両方保持できて効率的に書けるのでは？と思い実装してみました。

# 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 deepestLeavesSum(self, root: TreeNode) -> int:
        ans = {}
        count = 0
        self.dfs(root,ans,count)
        
        return ans[max(ans)]
        
    def dfs(self,node,ans,count):
        if node:
            if node.left:
                self.dfs(node.left,ans,count+1)
            if node.right:
                self.dfs(node.right,ans,count+1)
        if count not in ans:
            ans[count] = node.val
        else:
            ans[count] += node.val
# Runtime: 104 ms, faster than 46.02% of Python3 online submissions for Deepest Leaves Sum.
# Memory Usage: 17.4 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.

dfs関数の中でcountのインデックスと等しければ加算、それ以外の場合は値をそのまま代入する、という形式を取りました。
ansの中での最大値を返せば最終的に最も深い葉の値が返ってくる、というものです。
しかし、この答えではあまり速くないですね・・・

discussを観測した範囲では以下の回答がPythonで最速ではないかと思います。

# 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 deepestLeavesSum(self, root):
        q = [root]
        while q:
            pre, q = q, [child for p in q for child in [p.left, p.right] if child]
        return sum(node.val for node in pre)
# Runtime: 84 ms, faster than 98.04% of Python3 online submissions for Deepest Leaves Sum.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.

にしてもめちゃくちゃ速いですね・・・
今のところはこんなコード書けそうにないですが、こういったコードを読めるのは非常に面白いですね。

こうしたらこんなに速くなったよ！という例がありましたらコメント欄でコードとメモリ消費量とランタイムを書いて工夫した点を教えていただけると幸いです。