二分探索木の検索実装 CoffeeScript(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
N 個の整数 t1, t2, ..., tN が与えられます。
次のルールに従って二分探索木を作成してください。
さらに、M 個の値 ai が 与えられます。 ai が木に含まれる場合、二分探索木を先行順で走査したときに ai を訪問する順番を、木に含まれない場合、 -1 を出力してください。
全てのノードについて、以下が成り立つ
・ 入力で与えられる t1, t2, ..., tN の順に二分探索木に挿入する
・ 左の子ノードの値は現在のノードの値よりも小さい
・ 右の子ノードの値は現在のノードの値よりも大きい
先行順について
先行順とは、根から順に左部分木、右部分木を訪問する操作方法です。
先行順は再帰を用いた以下のアルゴリズムによって実装できます。
・ 訪問したノードを出力する
・ 左の子がある場合、左の子を訪問する
・ 右の子がある場合、右の子を訪問する
・ 親ノードに戻る
木構造について
木構造は、ノード同士が関係性を持つことで作ることができます。
この問題で各ノードが持つべき情報は以下の通りです。
・ ノードの値
・ 先行順で訪れる順番
・ 左の子ノードの情報
・ 右の子ノードの情報
- 入力される値
-
N
t1 t2 ... tN
M
a1 a2 ... aM
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
M 個の値 ai について M 行で出力して下さい。
N 個のノードで作成した木の中に ai と同じ値がある場合は、先行順で ai を訪れる順番を、ない場合は -1 と出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 3 ≦ N ≦ 100
・ 1 ≦ M ≦ 100
・ 1 ≦ ti ≦ 1000
・ 1 ≦ ai ≦ 1000
・ ti ≠ tj (i ≠ j)
- 入力例1
-
5
1 2 3 4 5
3
2 4 6
- 出力例1
-
2
4
-1
- 入力例2
-
7
4 2 5 3 1 6 7
5
10 4 8 3 7
- 出力例2
-
-1
1
-1
4
7
