https://leetcode.com/problems/path-sum/solution/
ノードがリーフでない場合は、子に対してhasPathSumメソッドを再帰的に呼び出し、合計を現在のノードの値だけ減らす。
ノードがリーフの場合、現在の合計がゼロであるかどうか、つまり最初の合計が検出されたかどうかを確認します。
Base case は、root が none ということはリーフの下の node を確認してるので、sum が 0 になっていないので False を返す。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
targetSum -= root.val
if not root.left and not root.right: # if reach a leaf
return targetSum == 0
return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)