ゼロから始めるLeetCode Day99 「112. Path Sum」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day98「39. Combination Sum」

次回
ゼロから始めるLeetCode Day100「108. Convert Sorted Array to Binary Search Tree」

Twitterやってます。

問題

112. Path Sum
難易度はEasy。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、二分木と和が与えられたとき、その木がルートから葉へのパスを持ち、パスに沿ってすべての値を加算すると、与えられた和に等しくなるかどうかを判断してください、というものです。

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

解法

スタックを使って解きました。

# 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 hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        stack = []
        stack.append((root,sum-root.val))
        while stack:
            node,sum = stack.pop()
            if not node.left and not node.right and sum == 0:
                return True
            if node.left:
                stack.append((node.left,sum-node.left.val))
            if node.right:
                stack.append((node.right,sum-node.right.val))       
        return False
# Runtime: 48 ms, faster than 55.07% of Python3 online submissions for Path Sum.
# Memory Usage: 15.6 MB, less than 52.21% of Python3 online submissions for Path Sum.

と言っても、結局dfsで網羅しながらsumから各valを引いてそれが0になればTrueを、そうじゃないならFalseを返すというだけの実装です。
別にstackを使わなければならない要素はそこまでありません。
値の管理がしやすいかな？と思って使ってみました。

それで通ったのでまあ良いのかなと。
Easyですし問題も複雑ではないのでこういうところで気づいたことはどんどん試していきたいですね。

では今回はここまで。お疲れ様でした。