問題
二分木のroot と、target をtarget にtrue、false を
- 葉とは、
左の 子も 右の 子も 無い節の ことです。 道は 必ず根から 始まり、 葉で 終わります - 各節は
val(値)、left(左の子)、 right(右の子) を 持ちます。 子が 無い ところは、 Python では None、JavaScript では nullです - 木が
空の ときは、 道が 1 本も 無いので falseを返します - 節の
数は 0 以上 500 以下、 値は -1000 以上 1000 以下で、 負の 数も あります。 targetは -100000 以上 100000 以下です
例では、null です。
入力と出力の例
例 1
根 6 から 3、
入力
root = [6, 3, 9, -2, 4, null, 1]
target = 7出力
true例 2
途中の 4 と 3 で
入力
root = [4, 3, null, -2]
target = 5出力
true例 3
根の 1 だけで
入力
root = [1, 2]
target = 1出力
false面接での聞かれ方
面接では、
- 「二分木と
数が 渡されます。 根から 葉まで 足して、 その 数に なる道は ありますか」 - 書き終えた
あとに 「その 道その ものを 返せますか？」 「当てはまる 道を 全部返せますか？」と 広げて 聞かれます - 「再帰を
使わずに 書けますか？」と 聞かれる こともあります
書き始める
まず
段 1
まずはtarget と
段 2
道をtarget から
段 3
あとは、true です。false が
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def has_path_sum(root, target):
if root is None:
return False
target -= root.val
left = root.left
right = root.right
if left is None:
if right is None:
return target == 0
found = has_path_sum(
left, target
)
if found:
return True
return has_path_sum(
right, target
)JavaScript
JavaScript
function hasPathSum(
root, target
) {
if (root === null) {
return false;
}
target -= root.val;
const { left, right } = root;
if (left === null) {
if (right === null) {
return target === 0;
}
}
const found = hasPathSum(
left, target
);
if (found) {
return true;
}
return hasPathSum(
right, target
);
}左のTrue (JavaScript では true) を
計算量
- 時間は O(n) です。
どの 節にも 多くて 1 回ずつ行きます - 使う
記憶は O(h) です。 h は 木の 高さで、 再帰の 呼び出しが 根から 葉までの 深さの 分だけ積み重なります - 木が 1 本道に
偏ると h は n と 同じに なり、 記憶は O(n) です
よく
- 合計が
目標を 超えたら 打ち切る。 値に 負の 数が あるので、 超えた あとに 減って 目標へ 戻る ことがあります。 例 2 では 4 と 3 で 7 に なっても、 次の -2 で 5 に 届きます。 正の 数だけと 決まっていない 限り、 途中では 打ち切れません - 葉で
ない節で 答えを決める。 残りが 0 に なった 時点で trueを返すと、 まだ子が ある 節で 止めてしまいます。 例 3 では 根の 1 で 残りが 0 に なりますが、 根は 葉ではないので 答えは falseです - 子が 1 つだけの
節を 葉と思う。 「左の 子が 無いから 終わり」としてしまうと、 右にだけ続く 道を 見落とします。 葉は、 左も 右も 無い節だけです
面接での
書き始める
「道を
全部書き出さなくても、 残りの 数を 子へ 渡していけば 足ります。 葉に 着いた ときだけ、 残りが 0 か どうかで 答えます。 値に 負の 数が あるので、 途中で 目標を 超えても 打ち切りません。 時間は O(n)、 記憶は 木の 高さの 分です。」
書き終えたら、
「例 2 で
たどります。 根の 4 で 残りは 1、 次の 3 で 残りは -2 に なり、 目標を 超えています。 ここで 打ち切らずに 進むと、 葉の -2 で 残りが 0 に なるので trueです。負の 数が ある ときに 打ち 切ってはいけない 理由が、 この 例で 分かります。」