アルゴリズムとデータ構造

二分木の中順走査 (In-order Traversal)

木の中順走査は再帰的な手順で、まずノードの左部分木を訪れ、続いてそのノードを訪問し、最後に右部分木を訪問します:
  1. 左部分木 (node.left) を訪問
  1. 現在のノードを訪問
  1. 右部分木 (node.right) を訪問
イメージとしては、二分木を根から吊るして、左から右へ順番に読んでいくような感覚です。
与えられた二分木に対して、中順走査を実行するよう求められます。

Input

入力は、二分木の各ノードに入っている値を空白区切りで表しています。値の並び順は、常に左部分木から右部分木へ進みながら取得した順序です。0 の値は、その位置にノードが存在しないことを示します。入力される二分木が正しい構造であることは保証されています。

Output

中順走査を行った結果、二分木のノードに格納されている値を空白区切りで出力してください。

Examples

Input
Output
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0
8 4 9 2 5 1 6 3 7
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0
8 4 2 5 1 6 3 7
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0
4 2 5 1 6 3 8 7 9
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0
4 2 7 5 8 1 3 6

解説

  1. Example 1:
      2. notion image
  1. Example 2:
      2. notion image
  1. Example 3:
      2. notion image
  1. Example 4:
      2. notion image
 
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue