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

二分木のポストオーダー（後順）走査

ツリーのポストオーダー走査は、再帰的な手順で行われます。具体的には、ノードの左部分木を先に処理し、次に右部分木を処理し、その後でノード自身を処理します。
  1. 左部分木を訪問する (node.left)
  1. 右部分木を訪問する (node.right)
  1. 現在のノードを訪問する
二分木が与えられたとき、そのツリーに対してポストオーダー走査を行うことが求められます。

入力

入力は、二分木のノードに含まれる値が空白区切りで与えられています。値の順序は、常に左から右の部分木へと順に走査している形式です。0 の値は、そのノードが存在しないことを示します。この入力が表す二分木は有効であることが保証されています。

出力

プログラムは、ポストオーダー走査を行った結果のノードの値を、空白区切りで出力しなければなりません。

例

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

解説

  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