LeetCode / Path Sum

（ブログ記事からの転載）

[https://leetcode.com/problems/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,

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

binary treeの先端から末端までのroot-to-leafの合計値が、変数sumの値と合致する箇所があるかどうかを判定する問題です。

解答・解説

解法1

recursiveを使った解法。
recursiveにrootの値を辿っていくときに、sum -= root.valとしてsumを減じていき、sum == root.valとなればTrueを返す、それがないまま末端のrootまで到達してしまったらFalseを返す、という処理。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        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)

解法2

Iterativeな解法。
Iterationを回す過程で、(root, root.val)のタプルの形式で変数stackに格納しつつ、curr, val = stack.pop()で先にstackに格納されたタプルを取り出し、valがsumと同値かどうか判定します。

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        stack = [(root, root.val)]
        while stack:
            curr, val = stack.pop()
            if not curr.left and not curr.right:
                if val == sum:
                    return True
            if curr.right:
                stack.append((curr.right, val+curr.right.val))
            if curr.left:
                stack.append((curr.left, val+curr.left.val))
        return False