🚀

112. Path Sum

に公開
PHP
LeetCode
tech

バイナリツリーのルートと整数 targetSum が与えられたとき、ルートからリーフまでのパスが存在し、そのパス上のすべての値を合計すると targetSum と等しくなる場合に true を返します。

リーフ とは、子を持たないノードのことです。

例 1:

入力:

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

出力:

true

説明:
ルートからリーフまでのパスで、合計が 22 になるパスが存在します。

例 2:

入力:

root = [1,2,3], targetSum = 5

出力:

false

説明:
ツリーには以下の2つのルートからリーフまでのパスがあります:

  • (1 --> 2): 合計は 3 です。
  • (1 --> 3): 合計は 4 です。
    どちらのパスも sum = 5 にはなりません。

例 3:

入力:

root = [], targetSum = 0

出力:

false

説明:
ツリーが空であるため、ルートからリーフまでのパスは存在しません。

  • 再帰 (DFS)
  • 幅優先探索 (BFS)

Discussion