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