二分木の平衡判定
木が平衡している、とは「どのノードで見ても、左の高さと右の高さの差が 1 以下」という状態です。根だけ見て済む話ではありません。
根では釣り合って見えても、下で崩れている
根の左右が同じ高さでも、左の枝のさらに奥で片側だけ 3 段伸びていれば、そこは平衡ではありません。判定の対象は全ノードです。1 か所でも差が 2 以上あれば、木全体として不合格になります。
1 の左に 2、その 2 の左に 3 だけがつながった木で考えてみます。根から見ると左の高さは 2、右は 0 で、差は 2。この 1 か所だけで木全体が不合格です。
なぜそこまで気にするのかというと、崩れた木は前のレッスンで見たとおり段数が伸びるからです。データベースの索引が挿入のたびに形を整え直しているのは、放っておくと入ってくる順番次第で木が簡単に一直線へ育つためです。
全ノードで測ると、同じ場所を何度も測り直す
素直に書くと、あるノードで左右の高さを測り、それから子へ降りて同じことを繰り返す形になります。ところがこれは、上のほうほど無駄が大きくなります。根で全体を測り、次に左の子でその中身をもう一度測り、その子でまた測る。深いところの葉は、段数の分だけ繰り返し歩かれます。
高さは 1 回測れば足りるはずです。下から持ち上がってくる途中で判定も済ませてしまえば、木全体を 1 度歩くだけで終わります。
測りながら、壊れた時点で打ち切る
戻り値に、測った値とは別の意味を持つ番人を混ぜます。フォルダの合計容量を出しつつ、壊れたファイルが 1 つでもあれば集計をやめる、という例で見てみます。
Python
def total_size(node):
if node is None:
return 0
if node.broken:
return -1 # 番人
left = total_size(node.left)
if left == -1:
return -1 # 見つけたら、そのまま上へ渡す
right = total_size(node.right)
if right == -1:
return -1
return node.size + left + right容量は必ず 0 以上なので、-1 は「壊れていた」以外の意味を持ちません。だから戻り値 1 つで、測った結果と異常の有無を同時に運べます。
左で見つけた時点で右へは降りません。呼び出した側も同じことをするので、異常は根まで一気に伝わり、途中の集計は 1 回も走りません。全部歩いてから最後に判定する書き方と比べて、無駄が消えます。
平衡判定も同じ形にできます。高さは必ず 0 以上と決まっているので、番人には負の値が使えます。左右から返ってきた値を見て、番人ならそのまま上へ渡す。番人でなければ差を確かめて、大丈夫なら高さを、駄目なら番人を返す。これで 1 度歩くだけで全ノードの判定が終わります。
戻り値が 2 つの意味を持つので、呼び出した直後の確認を飛ばすと壊れます。左を確かめずに右へ降りると、打ち切りの効果が消えるうえ、番人の値をそのまま高さとして計算してしまいます。
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 全ノードで左右部分木の高さの差が 1 以下なら true を返す
- 空の木 ([]) や [null] は true として扱う
入出力例
isBalanced([1,2,3,null,4]) → true
isBalanced([1]) → true
isBalanced([1,2,3,4,5,6,7]) → true
isBalanced([1,2,null,3]) → false
isBalanced([1,null,2,null,null,null,3]) → false
isBalanced([1,2,3,4,null,null,null,5]) → falseヒント
