CodeIQ過去問集29：共通の祖先は？
本稿はCodeIQで2014年12月22日～2015年1月26日に出題された コード銀行：共通の祖先は？ という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。
共通の祖先は？
次のような二分木があります。
各ノードの値はノード固有の番号で、根は必ず0であるものとします。 このとき、7と8のノードはいずれも5の子になっています。
4と7のノードに注目すれば、それぞれの親ノードは異なりますが、4の祖先・7の祖先は0で同じノードです。
このように、2つのノードから見て共通の親・祖先が存在するとき、2つのノードから最も近いものを見つけてください。「最も近い」は、各ノードの上位ノードで最初に共通するものという意味です。たとえば次のような場合
3と6のノードの祖先は0と1ですが、2つのノードに近い祖先は1です。
ところで、2と8に着目すると2は8の祖先になっています。
このように、一方のノードがもう一方の祖先になっている場合は共通の祖先を考えないことにします。
【問題】
二分木のデータファイルと、2つのノード番号のセットが複数書かれたファイルが与えられます。 これらのデータを読み込み、各ケースについて、2つのノードの共通する、最も近い祖先のノード番号を出力してください。 ただし、片方のノードがもう片方のノードの祖先になっている場合は、"NA"と出力してください。
【入力】
入力ファイルは2種類あります。
◆ファイルＡ
二分木のデータファイルです。1行目にノードの個数N、2行目から(N+1)行目までの各行に、(1)ノード番号、(2)左の子ノード番号、(3)右の子ノード番号が書かれています。ノード番号は0以上の整数で重複することはありません。子ノード番号が、その二分木のノード番号として存在しない場合は、子ノードが存在しないものとします。最初の例の二分木は、次のように表されます。
例
9 0 1 2 1 3 4 2 5 -1 3 -1 -1 4 6 -1 5 7 8 6 -1 -1 7 -1 -1 8 -1 -1
◆ファイルＢ
2つのノードセットが書かれたファイルです。1行目にデータセットの個数N、2行目から(N+1)行目までの各行に、2つのノード番号が書かれています。
例
4 7 8 4 7 3 6 2 8
【出力】
ファイルＢのデータセット毎に、改行区切りで共通の祖先で各ノードから最も近いノード番号を出力してください。一方のノードがもう一方のノードの祖先になっている場合は"NA"と出力してください。
例
5 0 1 NA
【解答方法】
bintree.zipをダウンロードしてください。 中には以下のファイルが含まれています。
- sample.a.in.txt, sample.b.in.txt, sample.out.txt
例で示したデータと、その解答です。
- testdata.a.in.txt, testdata.b.in.txt
これを入力として、正しい実行結果が得られるプログラムを書いてください。
（解答・解説は後日）
