ゼロから始めるLeetCode Day32「437. Path Sum III」

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day31「581. Shortest Unsorted Continuous Subarray」

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

Twitterやってます。

そういえば一ヶ月分続きました。めでたい。

問題

437. Path Sum III
難易度はeasy。
Top 100 Liked Questionsのeasyがこれを入れて残り三問となりました。

各ノードに整数値が含まれている二分木が与えられます。

ノードの値を合計して特定の値sumになるパスの数を求めます。

経路は親または葉で開始または終了する必要はありませんが、下方向に移動する必要があります（親ノードから子ノードへの移動のみ）。

なお、ツリーのノード数は1,000以下で、値の範囲は-1,000,000〜1,000,000です。

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1. 5 -> 3

1. 5 -> 2 -> 1
2. -3 -> 11

解法

再帰を使ったdfsで解きました。

# 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 pathSum(self, root: TreeNode, sum: int) -> int:
        def dfs(root,sums,start):
            if not root:
                return 0
            sums -= root.val
            if sums == 0:
                self.ans += 1
            dfs(root.left,sums,False)
            dfs(root.right,sums,False)
            if start:
                dfs(root.left,sum,True)
                dfs(root.right,sum,True)
        dfs(root,sum,True)
        return self.ans
# Runtime: 940 ms, faster than 24.67% of Python3 online submissions for Path Sum III.
# Memory Usage: 15.1 MB, less than 6.82% of Python3 online submissions for Path Sum III.

最初はrootとsumsだけでかけるかと思って書いていたのですが、どうもそれだけでは書けなかった（書けるかもしれないが今の私の頭では思いつかなかった）ので、discussを覗いたらほとんど一緒の解答があり、そこでは現在のnodeを始点として扱うためにbooleanを用いており、非常にすっきりとした実装ができたのでそのままこちらを載せておきます。

それにしてもアルゴリズム強い人すごい・・・

もっと精進しなければならないですね。

良さげな解答があれば追記します。