問題
二分木のroot を
- 各節は、
値 val、左の 子 left、右の 子 rightを持ちます。 子が 無い ところは、 Python では None、JavaScript では nullです - 例では、
木を 上の 段から 順に、 各段を 左から 右へ 読んだ値の 並びで 書きます。 子が 無い ところは nullです。空の 木は root = []です - 節の
数は 0 以上 1000 以下、 値は どれも -1000 以上 1000 以下です
入力と出力の例
例 1
根 4 の
入力
root = [4, 7, 2, null, 5, 1]出力
3例 2
左の
入力
root = [1, 2, null, 3, null, 4]出力
4例 3
空の
入力
root = []出力
0面接での聞かれ方
面接では、
- 「二分木の
最大の 深さを 返してください」 - 書き終えた
あとに 「再帰を 使わずに 書けますか？」と 続けて 聞かれます - 「木が
とても 深いと、 何が 困りますか？」と、 再帰の 深さを 聞かれる こともあります
深さを
まず
段 1
まずは
段 2
根から
段 3
再帰の
段 4
再帰を
ここから解答です。先に自分で書いてから読むと、考え方が残ります。
解答
Python
Python
def tree_depth(root):
if root is None:
return 0
lh = tree_depth(root.left)
rh = tree_depth(root.right)
return max(lh, rh) + 1JavaScript
JavaScript
function treeDepth(root) {
if (root === null) {
return 0;
}
const { left, right } = root;
const lh = treeDepth(left);
const rh = treeDepth(right);
return Math.max(lh, rh) + 1;
}空の
計算量
- 時間は O(n) です。
どの 節も 1 回ずつ訪れます - 使う
記憶は O(h) です。 h は 木の 深さで、 再帰の 呼び出しが h 段まで 積み重なります。 例 2 のように 片側に 伸びた 木では、 h は n と 同じになります - 段 4 の
幅優先の 書き方も、 時間は O(n) です。 記憶は 1 つの 段に 並ぶ節の 数だけ使います
よく
- 空の
木を 考えない。 先に root.leftを読むと、 空の 木で 落ちます。 空なら 0 を 返す行を 一番先に置きます - 葉で
止めようとして 子が 片方の 節で 間違える。 「左右とも空なら 1」だけを 止まる ところに すると、 子が 片方だけの 節で 空の 側を 読みに 行って 落ちます。 空の 木を 0 と する 1 か所に まとめると安全です - 大きい方でなく
小さい方を取る。 深さは 一番遠い 葉までなので、 左右の 大きい方を 取ります。 小さい方を 取ると、 一番近い 葉までの 段の 数という 別の 答えになります
面接での
書き始める
「深さは、
左右の 子の 木の 深さの 大きい方に 1 を 足した数です。 空の 木を 0 段として、 再帰で 書きます。 どの 節も 1 回ずつ 見るので 時間は O(n)、 記憶は 木の 深さの 分だけ 使います。」
書き終えたら、
「例 1 で
たどります。 7 は 下の 5 が 1 段なので 2 段です。 2 も 下の 1 が 1 段なので 2 段です。 根の 4 は 2 段と 2 段の 大きい方に 1 を 足して 3 段に なります。 再帰が 深くなりすぎるのが 心配なら、 段ごとに 数える 幅優先でも 書けます。」