二分木の高さ

木の高さは、根から一番深い葉まで何段あるかです。この数がそのまま、探すときに最悪何回たどるかになります。同じ件数を入れても、段数が伸びた木はそれだけ遅い木です。

上から数えると、どの枝が一番長いか最後まで決まらない

根から 1 段ずつ数えていっても、分かれ道のたびに「こちらのほうが長いかもしれない」が残ります。全部の葉まで降りて、届いた深さを覚えておいて、最後に一番大きいものを選ぶ。覚えておく場所が要りますし、書き方も回りくどくなります。

向きを変えます。自分で数えるのをやめて、子に聞くのです。

下に聞いてから、自分の 1 段を足す

まず、高さではなくノードの個数を数える形で見てみます。

def size(node):
    if node is None:
        return 0
    return 1 + size(node.left) + size(node.right)

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

このコースでは段の数、つまり通るノードの個数で数えます。空を 0 にしたまま自分のぶんの 1 を足し忘れると、葉もその親も 0 になり、すべてのノードが 0 を返してしまいます。枝の本数で数える別の流儀では、空を -1 にして、1 + max(...) の形は残します。すると葉が 0 になります。他人のコードを読むときは、空で返す値と、自分のぶんの 1 の両方を見てください。

段数を気にする理由は最初に書いたとおりです。100 万件を入れても、きれいに枝分かれしていれば 20 段ほどで底に着き、一直線に伸びていれば 100 万段になります。同じデータ、同じ探し方でも、形だけでこれだけ違います。

演習の heightAt(tree, i) は height と同じ段に置き、木を引数で渡します。たとえば heightAt(tree, 2 * i + 1) が左の子への再帰です。入れ子の関数は使いません。

1. tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
2. ノードがない場合は高さ 0、ノード 1 つの場合は高さ 1 を返す
3. 再帰または反復で実装すること