時間制限 : sec, メモリ制限 : KB
English / Japanese  

木の巡回

以下に示すアルゴリズムで、与えられた2分木のすべての節点を体系的に訪問するプログラムを作成してください。

  1. 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
  2. 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
  3. 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます。

与えられる2分木は $n$ 個の節点を持ち、それぞれ $0$ から $n-1$ の番号が割り当てられているものとします。

入力

入力の最初の行に、節点の個数 $n$ が与えられます。続く $n$ 行目に、各節点の情報が以下の形式で1行に与えられます。

$id$ $left$ $right$

$id$ は節点の番号、$left$ は左の子の番号、$right$ は右の子の番号を表します。子を持たない場合は $left$ ($right$) は -1 で与えられます。

出力

1行目に"Preorder"と出力し、2行目に先行順巡回を行った節点番号を順番に出力してください。

3行目に"Inorder"と出力し、4行目に中間順巡回を行った節点番号を順番に出力してください。

5行目に"Postorder"と出力し、6行目に後行順巡回を行った節点番号を順番に出力してください。

節点番号の前に1つの空白文字を出力してください。

制約

  • $1 \leq n \leq 25$

入力例 1

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

出力例 1

Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0

参考文献

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.