二分木のポストオーダー（後順）走査
ツリーのポストオーダー走査は、再帰的な手順で行われます。具体的には、ノードの左部分木を先に処理し、次に右部分木を処理し、その後でノード自身を処理します。
左部分木を訪問する (
node.left)右部分木を訪問する (
node.right)現在のノードを訪問する
二分木が与えられたとき、そのツリーに対してポストオーダー走査を行うことが求められます。
入力
入力は、二分木のノードに含まれる値が空白区切りで与えられています。値の順序は、常に左から右の部分木へと順に走査している形式です。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:
例 2:
例 3:
例 4:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB