ALDS1_7_D: Reconstruction of the Tree

チャレンジ問題
二分木をpreorderで巡回した結果とinorderので巡回した結果を入力として受け取り、
その二分木をpostorderで巡回したときの結果を出力せよ、というもの
見るからにパズルチックで問題のとおりにコード書けば解けるってものではなさそう

どこから手を付けていいかもわからない
なにかやり方があって一発で求められるのか、
いろいろ可能性があって探索していくのか

preorderとinorderだけで木が一意に決まるものなのか
一意には決まらないけどpostorderの結果はひとつしかないとか
（あまりありそうな気はしないけど）

節点の数が100以下ってことは探索、しかもけっこうオーダの高い探索なのかな？

さっぱりわからんのでn=1から木を具体的に書いてみる
こういうのは紙だな

n=1のときは木は1通り
n=2のときは4通り
n=3のときは36通り(12個めまで書いて挫折
総当たりはとんでもないことになりそうだ
ありうる木の可能性はこうなると思う

def sort_of_trees(n):
    s = 1
    for k in range(n):
        s *= (n - k) * (2 * k - (k - 1))
    return s

for n in range(1, 10):
    print(n, ":", sort_of_trees(n))

1 : 1
2 : 4
3 : 36
4 : 576
5 : 14400
6 : 518400
7 : 25401600
8 : 1625702400
9 : 131681894400

preorderが条件に合う木の中でinorderも条件に合うものを探す、とかじゃないと無理？

全部のpreordeを満たす木を造って調べる？
どうやって全種類作ればいい？

preorderの最初の要素を根にして
そのあとpreorderの順に全部左へ追加していくとpreorderを満たす木になるので
そのあとpreorderを崩さないようにちょっとずつ変形しながら
inorderを満たす木を探す、みたいなやり方かなー
うまく全部調べられるやり方あるかなあ

preorderを満たす木は何通りあるんだろう
こっちは式は立てられなかったけど数えてみると

n=1 : 1通り
n=2 : 2通り
n=3 : 5通り
n=4 : 14通り
n=5 : 41通り(たぶん)

でそれでもやっぱり大変なことになりそう
規則性は見えてないんだけど3倍して1をひくと次の答えになるのは偶然かなあ

ということはもっと狙いを絞ってつくらないといけないのか
わかりやすいところではinorderの最初の要素が左端に来るとかあるので
なにかやれそうではある
具体的にはわからない

これはスルーか