二分木の中順走査 (In-order Traversal)
木の中順走査は再帰的な手順で、まずノードの左部分木を訪れ、続いてそのノードを訪問し、最後に右部分木を訪問します:
左部分木 (
node.left) を訪問現在のノードを訪問
右部分木 (
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 |
解説
Example 1:
Example 2:
Example 3:
Example 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB