二分木の post-order 走査
木を使い終わり、ノードを 1 つ残らず解放する場面を考えます。手でメモリを返す言語では、ここを間違えると二度と使えない領域が残り続けます。
親を先に消すと、子に手が届かない
根から消していくとどうなるでしょうか。根を解放した瞬間、そこに書いてあった左と右の行き先も一緒に消えます。
Python
def wrong_free(node):
if node is None:
return
free(node) # 先に自分を消した
wrong_free(node.left) # もう読めない場所を読んでいる
wrong_free(node.right)運が良ければその場で落ちます。悪ければ、すでに他の用途へ配られた領域を読み、まったく無関係な値をノードとして扱い始めます。落ちる場所と原因が離れるので、追いかけるのがとても難しいバグになります。
子を片付けてから、自分を片付ける
順序を入れ替えるだけで解決します。
Python
def free_tree(node):
if node is None:
return
free_tree(node.left)
free_tree(node.right)
free(node) # 自分は最後左、右、自分。これが post-order です。自分を消す時点で、下にぶら下がっていたものはすべて片付いています。裏を返せば、自分を触るまでは子の情報が生きている、ということでもあります。
根が 1、左が 2、右が 3 の木で追ってみます。左へ降りて 2 を片付け、右へ降りて 3 を片付け、戻ってきて 1 を片付ける。並べると 2, 3, 1 です。根が最後にいるのが post-order の顔です。
下から答えを持ち上げる形は、全部これになる
解放だけの話ではありません。子の計算結果を受け取ってから自分の値を決める処理は、必ずこの順になります。フォルダの合計容量、部下の総数、閉じタグを書き出す順番。どれも下が確定するまで上が決まりません。
たとえばタグを組み立てる処理も同じ形です。
Python
def to_html(node):
if node is None:
return ""
inner = to_html(node.left) + to_html(node.right)
return "<" + node.tag + ">" + inner + "</" + node.tag + ">"中身が全部できあがるまで、閉じタグは書けません。だから子を先に組み立て、そのあとで自分の開きと閉じで挟みます。
逆に、自分の値が先に決まるなら post-order である必要はありません。単に値を並べるだけなら、どの順でも全ノードを 1 回ずつ訪れます。順序を選ぶ基準は「上が下の答えを必要とするかどうか」です。ここが分かると、木の問題でどの順を選ぶかで迷わなくなります。
書くときに間違えやすいのは、右の再帰の書き忘れです。左だけ書いても動いてしまい、左端の枝だけをたどって終わります。結果の件数がノードの数と合わないときは、まずここを疑ってください。もう 1 つは行き止まりの判定です。配列で受け取っている以上、範囲の外に出ていないかと、その場所が空でないかの両方を確かめる必要があります。片方だけだと、深い木で必ず落ちます。
なお、走査した結果を並べたとき、末尾に根が来ていれば post-order です。手元の出力がどれなのか分からなくなったら、最後の 1 件を見てください。
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 再帰または反復で left -> right -> root の順に訪問する
- 戻り値は訪問順の値の配列。null は結果に含めない
入出力例
postorder([1,2,3,null,4]) → [4,2,3,1]
postorder([1]) → [1]
postorder([1,2,3]) → [2,3,1]
postorder([1,null,2,null,null,null,3]) → [3,2,1]
postorder([1,2,3,4,5,6,7]) → [4,5,2,6,7,3,1]
postorder([5,3,8,1,4,null,9]) → [1,4,3,9,8,5]ヒント
