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

二分木の先行順走査 (Pre-order traversal)

木の先行順走査は再帰的に処理を行う方法で、まず現在のノードを訪問し、その後左部分木を訪れ、続いて右部分木を訪れます:
  1. 現在のノードを訪問する
  1. 左部分木 (node.left) を訪問する
  1. 右部分木 (node.right) を訪問する
与えられた二分木に対して、この先行順走査を行う必要があります。

入力

入力として、スペース区切りの整数が与えられます。これは二分木のノードの値を表しています。値の並びは、以前の説明で示されたように、常に左部分木から右部分木へと進む形で与えられます。0 はそのノードが存在しないことを意味します。入力される二分木は有効であることが保証されています。

出力

先行順走査を行ったとき、二分木の各ノードの値をすべてスペース区切りで出力します。

例

入力
出力
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0
1 2 4 8 9 5 3 6 7
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0
1 2 4 8 5 3 6 7
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0
1 2 4 5 3 6 7 8 9
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0
1 2 4 5 7 8 3 6

解説

  1. 例 1:
      2. notion image
  1. 例 2:
      2. notion image
  1. 例 3:
      2. notion image
  1. 例 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