Path Sum
二分木が配列 tree にレベル順で格納されており、数値 targetSum が与えられます。根はインデックス 0 にあり、インデックス i のノードの子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を表し、配列の末尾に余分な -1 が含まれることがあります。根から葉までのいずれかの経路上の値の合計が targetSum になる場合は true を返し、そうでない場合は false を返してください。葉とは、左右両方の子の位置が空であるノードです。
関数
- treeinteger-array
- 二分木をレベル順に並べ、空の位置には -1 を使用します
- targetSuminteger
- 根から葉への経路が到達すべき合計
- 戻り値boolean
- 根から葉へのパスの合計がtargetSumになるものがあれば true、そうでなければ false
制約
1 ≤ tree.length ≤ 32767- 各
tree[i]は-1、または0 ≤ tree[i] ≤ 1000を満たす値です。 tree[0]は決して-1ではないため、木には少なくとも 1 つのノードがあります。- 配列の末尾には、最後のノードの後に余分な
-1のエントリが含まれている場合があります。 - 空の位置の子はどちらも空で、深さは最大でも
14です。 0 ≤ targetSum ≤ 15000
例
- 入力
- tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
- 出力
- true
- 説明
- パス
3、9、2（インデックス0、1、4）の合計は14で、インデックス4の2は葉です。
- 入力
- tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
- 出力
- false
- 説明
3 + 9 = 12ですが、9には子があるため、そこで終わる経路はありません。根から葉までの3つの経路の合計は14、10、16で、12になるものはありません。
- 入力
- tree = [4, -1, -1]targetSum = 4
- 出力
- true
- 説明
- ルートの子の位置は両方とも空なので、ルートはそれだけで葉です。
4だけを含む経路の合計は4です。
発展問題
パスが任意のノードから始まり、その下にある任意のノードで終わる場合、targetSumになるパスの数を数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ルートから下へ進み、合計を累積していきます。その合計を
targetSumと比較できるのはどこですか？葉ノードでのみ、つまり2つの子の位置がどちらも空のノードでのみ該当します。子が1つあるノードは、合計がすでに一致していてもパスの終点にはなりません。これまでのパスの合計を各子へ引き継ぎます。
ペアのスタックを保持します。各ペアは、ノードのインデックスと、ルートからそのノードまでの合計です。ペアを1つ取り出し、そのノードが葉で、合計が
targetSumと等しければ、trueを返します。それ以外の場合は、実在する各子ノードを、その値を合計に加えてスタックに追加します。
解説
根から葉までの完全なパスだけが対象です。累計が、まだ子を持つノードでtargetSumに達しても、対象にはなりません。そこで、パスの合計をパラメーターまたはスタックで各ノードまで引き継ぎ、葉でのみ目標値と比較します。
残りの合計に対する再帰
考え方
targetSumになるパスはルートの値から始まるため、ルートの子の1つから始まる残りの部分の合計は、targetSumからその値を引いた値になる必要があります。これは、より小さな木で同じ問いを考えることです。下に進むたびに各ノードの値を引きます。葉ではパスが終わるので、残りが何もないかどうかが答えになります。
最初の例では、ルートで残りは14 - 3 = 11となり、9で2、葉の2で0になります。2つ目の例では、9ですでに残りが0になりますが、子があるため探索は続きます。各ノードは1回ずつ訪問するので、時間計算量はO(n)です。呼び出しスタックには各レベルにつき1つのフレームが保持され、最大で15個です。
アルゴリズム
walk(i, remaining)を書き、remainingからtree[i]を引きます。iの両方の子の位置が空（インデックスが末尾を超えている、または-1）の場合、remainingが0かどうかを返します。- そうでなければ、実在する左の子または実在する右の子に対する
walkがtrueを返す場合にtrueを返します。 walk(0, targetSum)を返します。
def hasPathSum(tree, targetSum):
n = len(tree)
def walk(i, remaining):
# remaining is what the path still needs once it reaches node i.
remaining -= tree[i]
left, right = 2 * i + 1, 2 * i + 2
has_left = left < n and tree[left] != -1
has_right = right < n and tree[right] != -1
if not has_left and not has_right:
return remaining == 0 # a leaf: the path ends here
return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))
return walk(0, targetSum)明示的なスタックを使った深さ優先探索
考え方
再帰では、呼び出しごとに1つの数値を保持します。代わりに、その数値を各ノードの横にあるスタックで管理しましょう。値は、根からそのノードまでの経路の合計です。(0, tree[0])から始めます。各子ノードには、親ノードの合計に自身の値を加えたものを割り当てます。ペアを取り出します。ノードが葉で、合計がtargetSumなら完了です。そうでなければ、実際の子ノードをスタックに追加します。
実際の各ノードは一度だけ追加されるため、時間計算量はO(n)です。スタックには各レベルで待機中の兄弟ノードが1つほど保持されるため、空間計算量はO(h)です。同じループは、再帰ではスタックが不足する可能性がある、深いポインタベースの木でも使えます。
アルゴリズム
(0, tree[0])をスタックにプッシュします。- ペア
(i, total)をポップし、子の位置2*i+1と2*i+2を確認します。 - どちらの子も実在せず、
totalがtargetSumと等しい場合は、trueを返します。 - 実在する各子
cを(c, total + tree[c])としてプッシュします。 - スタックが空になったら、
falseを返します。
def hasPathSum(tree, targetSum):
n = len(tree)
stack = [(0, tree[0])] # (node index, sum of the path from the root to it)
while stack:
i, total = stack.pop()
left, right = 2 * i + 1, 2 * i + 2
has_left = left < n and tree[left] != -1
has_right = right < n and tree[right] != -1
if not has_left and not has_right and total == targetSum:
return True # a leaf whose path adds up
if has_left:
stack.append((left, total + tree[left]))
if has_right:
stack.append((right, total + tree[right]))
return False
落とし穴と境界ケース
- 各ノードで合計を比較する。2つ目の例では、
3 + 9 = 12は子を持つ9の位置で一致するため、答えはfalseです。 - 空の子の位置でパスが終わることを見落とす。すると、2つ目の例の
9は、空の左の位置を通るパスを終点とします。 - ルートだけの場合を忘れる。単一ノードは葉なので、ターゲットが
4の[4]はtrueであり、ターゲットが0の[0]も同様です。 - 配列の末尾を越えて読み取る。末尾近くの葉は、最後の要素を越える子インデックスを持つことがあります。
- Lua と R のオフセットを混同する。ノードのインデックスは
2*i+1用に0始まりのままにし、tree[i + 1]を読み取ります。
よくある質問3
Path Sum の時間計算量はどのくらいですか？
O(n): 各ノードは最大 1 回だけ訪問され、条件に一致する最初の葉で探索を終了できます。追加の空間計算量は、探索中のパスのための O(h) であり、これは呼び出しフレームまたは自分で用意したスタック上の要素として使われます。
Path SumはBFSで解けますか？
はい。ノードとその経路の合計値のペアをスタックではなくキューに入れ、取り出すたびに各葉ノードを確認します。時間計算量は引き続き O(n) ですが、キューには1つのレベル全体、つまり完全二分木のノードの約半分が入ることがあります。一方、スタックに入るのは各レベルにつき約1つのノードです。
合計が目標値になるすべての経路を見つけるにはどうすればよいですか？
下へ進むにつれて現在の経路上のノードのリストを保持し、合計が一致する各葉でそのリストを答えにコピーして、上へ戻るときに最後のノードを削除します。走査方法は変わりません。一致する葉が多い場合、経路のコピーには走査よりもコストがかかることがあります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def hasPathSum(tree, targetSum):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
tree = [3, 9, 6, -1, 2, 1, 7] targetSum = 14
期待される出力
true