二分木の高さ
木の高さは、根から一番深い葉まで何段あるかです。この数がそのまま、探すときに最悪何回たどるかになります。同じ件数を入れても、段数が伸びた木はそれだけ遅い木です。
上から数えると、どの枝が一番長いか最後まで決まらない
根から 1 段ずつ数えていっても、分かれ道のたびに「こちらのほうが長いかもしれない」が残ります。全部の葉まで降りて、届いた深さを覚えておいて、最後に一番大きいものを選ぶ。覚えておく場所が要りますし、書き方も回りくどくなります。
向きを変えます。自分で数えるのをやめて、子に聞くのです。
下に聞いてから、自分の 1 段を足す
まず、高さではなくノードの個数を数える形で見てみます。
Python
def size(node):
if node is None:
return 0
return 1 + size(node.left) + size(node.right)JavaScript
function size(node) {
if (node === null) return 0;
return 1 + size(node.left) + size(node.right);
}自分では 1 つも数えていません。左に何個あるか聞き、右に何個あるか聞き、返ってきた数に自分のぶんの 1 を足して返すだけです。行き止まりが 0 を返すので、葉は 1 を返し、その親は 3 を返し、と下から積み上がっていきます。
聞かれた側が答えを返すだけなので、途中経過をどこかに覚えておく必要がありません。呼び出しから戻ってきた値はその場で使われて消えます。上から数えようとしたときに要った置き場が、まるごと不要になりました。
高さも同じ形で書けます。違うのは、左右から返ってきた 2 つの数をどう扱うかだけです。個数なら両方足しますが、高さは一番深いところまでの段数なので、2 つのうち片方しか使いません。どちらを使うかは、高さの定義をもう一度読めば決まります。
1 の下に 2 と 3 があり、2 の下に 4 だけがある木で追ってみます。4 は子がいないので、下からは 0 が 2 つ返り、自分のぶんを足して 1。3 も同じく 1 です。2 は左が 0、右が 1 なので、深いほうの 1 に自分のぶんを足して 2。根は左が 2、右が 1 なので、深いほうの 2 に足して 3 になります。
空を 0 にするか 1 にするか
行き止まりが返す値の決め方で、答えが 1 つずれます。
プレーンテキスト
空の木 -> 0
葉が 1 つだけ -> 1このコースでは段の数、つまり通るノードの個数で数えます。自分のぶんの 1 を足し忘れると、段の数ではなく枝の本数を返すことになり、葉が 0、空が -1 という別の流儀になります。どちらも世の中で使われている数え方なので、他人のコードを読むときは、まず空のときに何を返しているかを見てください。
段数を気にする理由は最初に書いたとおりです。100 万件を入れても、きれいに枝分かれしていれば 20 段ほどで底に着き、一直線に伸びていれば 100 万段になります。同じデータ、同じ探し方でも、形だけでこれだけ違います。
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- ノードがない場合は高さ 0、ノード 1 つの場合は高さ 1 を返す
- 再帰または反復で実装すること
入出力例
height([1,2,3,null,4]) → 3
height([1]) → 1
height([1,2,3]) → 2
height([1,2,3,4,5,6,7]) → 3
height([1,null,2,null,null,null,3]) → 3
height([5,3,8,1,4,null,9]) → 3ヒント
