LeetCodeに毎日挑戦してみた 112. Path Sum（Python、Go）

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

27問目（問題112)

112. Path Sum

問題内容

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum

Note: A leaf is a node with no children.

（日本語訳）

二分木と合計が与えられた場合、パスに沿ったすべての値の合計が与えられた合計に等しくなるように、ツリーにルートからリーフへのパスがあるかどうかを判別します。

注： リーフは子のないノードです。

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.

考え方

1. 再帰処理を用います

2. rootのleft,rightをそれぞれ潜っていって、引数として与えられた目標となるSumからvalを引いていき、0になったらreturnします。

3. 最終的に最初のrootのleftかrightに正解があればtrueどちらとも正解のルートがなければfalseが返されます

解答コード

class Solution:
    def hasPathSum(self, root, sum):
        if not root:
            return False

        if not root.left and not root.right and root.val == sum:
            return True

        sum -= root.val

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

• Goでも書いてみます！

func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return sum == root.Val
    }
    return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}
```LeetCodeに毎日挑戦してみた 111. Minimum Depth of Binary Tree（Python、Go）