二分木の幅優先走査 (BFS)
組織図を上から見ていくとします。まず経営層、次に部長がそろって何人、その下に課長が何人。段ごとにまとめて把握したい、という見方です。ここまでの走査では、これができません。
潜っていくと、同じ段の人がばらばらに出てくる
これまでの 3 つの走査は、分かれ道に来たら片方を最後まで降りてから戻ってきます。左の部長の下の課長も、そのまた下の主任も出し切ってから、ようやく右の部長が出てきます。同じ段にいる 2 人の間に、何十人も挟まってしまうわけです。
段ごとにまとめたいなら、潜るのを後回しにする必要があります。今の段の人を全員出し切ってから、次の段へ降りたい。再帰は「呼んだらその場で最後まで走る」ので、後回しにする置き場を自分で用意することになります。
順番待ちの列に並ばせる
やることは 1 つだけです。訪問する予定のノードを列に並べ、前から 1 つずつ呼び出します。呼び出したノードの子は、列の末尾に足します。
Python
from collections import deque
def by_layer(root):
names = []
waiting = deque([root])
while waiting:
person = waiting.popleft()
if person is None:
continue
names.append(person.name)
waiting.append(person.left)
waiting.append(person.right)
return names末尾に足して先頭から取り出すので、後から入った深い段の人が、先に並んでいた同じ段の人を追い越すことはありません。これが段ごとにそろう理由の全部です。
1 の下に 2 と 3、2 の下に 4 がある木で、列の中身を追ってみます。最初は 1 だけ。1 を呼ぶと列は 2, 3 になります。2 を呼ぶと 3, 4。3 を呼ぶと 4 だけが残り、最後に 4 が出ます。出てきた順は 1, 2, 3, 4 で、段の区切りどおりです。
取り出す側を変えると、性格が入れ替わります。
Python
waiting.popleft() # 前から取ると、段ごとにそろう
waiting.pop() # 後ろから取ると、深く潜っていく最後に入れた子がすぐ呼ばれるので、後者はそのまま 1 本の枝を降りていきます。同じ入れ物でも、どちら側から取り出すかだけで、幅を優先するか深さを優先するかが決まるわけです。
空の席まで並ばせてしまう
上のコードは、子がいるかを確かめずに列へ足しています。代わりに、取り出した直後に空かどうかを見て読み飛ばしています。入れる前に弾いても、出したあとに弾いてもかまいませんが、両方さぼると空の値が結果に混ざります。
配列で受け取っている場合は、確かめることが 1 つ増えます。子の番号が配列の外にはみ出していないか。ここを見ないと、葉のさらに先で範囲外を読みます。
もう 1 つ、Python では列に list を使わないでください。pop(0) は先頭を抜いたあとに残り全部を前へ詰め直すので、ノードが増えるほど重くなります。deque の popleft なら詰め直しは起きません。列に対して前から取り出す操作は、この走査で毎回発生します。
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- キュー (FIFO) を使ってレベル順に訪問する
- 戻り値は訪問順の値の配列。null は結果に含めない
入出力例
levelOrder([1,2,3,null,4]) → [1,2,3,4]
levelOrder([1]) → [1]
levelOrder([1,2,3]) → [1,2,3]
levelOrder([1,null,2,null,null,null,3]) → [1,2,3]
levelOrder([1,2,3,4,5,6,7]) → [1,2,3,4,5,6,7]
levelOrder([5,3,8,1,4,null,9]) → [5,3,8,1,4,9]ヒント
