25. Path Sum

読了目安約1分

Tree / LC 112 (Easy) — 根から葉への経路で合計が一致するか。

この章の目次

問題

LeetCode 112. Path Sum（Easy / カテゴリ: Tree）

二分木の根 root と整数 targetSum が与えられます。根から葉までの経路のうち、経路上の値の合計が targetSum に一致するものがあるかを返します。経路は必ず葉で終わります。途中のノードで合計が一致しても true ではありません。空の木は false です。

考え方

ヒント 1

根から 1 段下るたびに「残りいくら必要か」を更新して渡すと、部分木に対する同じ形の問題になります。

ヒント 2

再帰の骨組みは 3 行です。空の木なら false。葉なら「葉の値 == 残り」を返す。それ以外は、残りから自分の値を引いて左右のどちらかが true かを返す。

Swift 実装のポイント

葉の判定は root.left == nil && root.right == nil です。
ノードの値は負にもなり得るため、「合計が targetSum を超えたら打ち切る」枝刈りはできません。
|| は短絡評価なので、左の部分木で見つかれば右は探索されません。

模範解答

Swift
class Solution {
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
        guard let root = root else { return false }
        if root.left == nil && root.right == nil {
            return root.val == targetSum
        }
        let rest = targetSum - root.val
        return hasPathSum(root.left, rest) || hasPathSum(root.right, rest)
    }
}

計算量: O(N)。最悪ですべてのノードを訪れます。