【LeetCode】112. Path Sum 解答・解説【Python】

はじめに
問題
1. 原文
2. 内容
方針
解答
1. 解答1：
補足・参考・感想

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

問題

原文

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output: true

Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5

Output: false

Explanation: There two root-to-leaf paths in the tree: (1 –> 2): The sum is 3. (1 –> 3): The sum is 4. There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0

Output: false

Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

The number of nodes in the tree is in the range [0, 5000].

-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000

内容

二分木と整数型変数targetSumが与えられます。根から葉までの値を合計してtargetSumと一致する経路があればTrueを返してください。葉は子ノードを持たないノードです。

※正しくない可能性があります。

方針

・深さ優先探索

解答

解答1：

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        #木がない場合
        if not root:
            #Falseを返す
            return False
        #葉ノードであり、その値がtargetSumと同じである場合
        if not root.left and not root.right and root.val == targetSum:
            #Trueを返す
            return True
        #targetSumから木の値を差し引く
        targetSum = targetSum - root.val
        #ここまでの処理を左右の子ノードで行う
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

class Solution:

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

#木がない場合

if not root:

#Falseを返す

return False

#葉ノードであり、その値がtargetSumと同じである場合

if not root.left and not root.right and root.val == targetSum:

#Trueを返す

return True

#targetSumから木の値を差し引く

targetSum = targetSum - root.val

#ここまでの処理を左右の子ノードで行う

return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

・時間計算量はO(n)

・各ノードの値を合計してtargetSumになるかを調べるのではなく、各ノードの値をtargetSumから引き、葉ノードの時にその値とtargetSumが一致するかを判定しています。

補足・参考・感想

参考

前：111. Minimum Depth of Binary Tree

次：

LeetCode 解答・解説記事一覧