こんにちは
今回の学びは
pivotで左sub木と右sub木をどう分けられるか？を考えるのが鍵
問題はconstruct-binary-tree-from-preorder-and-postorder-traversal
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
この問題パッとみた時
にまず
・binary search treeであること
・postorderの場合rootは必ず最後に訪れるこ
ということが思い浮かぶかどうかだ。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
leetcodeの問題はbinary treeと言っているだけどbinary search treeではないことに気づこう。
まずは私は
https://www.geeksforgeeks.org/construct-a-binary-search-tree-from-given-postorder/
のbinary search treeのほうが簡単だとおもうので
こちらの解法に迫っていきたいと思う
例えば
[2, 4, 3 ,8, 7, 5]が与えられた時
5
/ \
3 7
/ \ \
2. 4. 8
という配列が与えられて,正解の二分検索木は上記のようである
・最後の数字はルートであること
・左の木は5以下なので5より小さい数字でもっとも高いindexを探す。つまりは普通に左から操作していってS[i]>=5となったところで止まる。そしてi-1す
る。こうすることで左のsub木が特定される。必然的に残りは右のsub木となる。
・上のことは、かならずsub木もまとめて印字されるという点、この特徴がつかめているかによって。これをいきなり見て思いつく人はやはりIQが高いと思う。わたしは思いつかなかったのでこれをパターンとして次回同じような問題に当たったときは発想できるようにするまでだと思う。
ま、こんな形で再起でとける
というのが一つ目の解法、これはtO(N^2)である。
擬似コードをかいてみる
def solve(S: List[int], l, r) -> TreeNode:
# l start
# r end (exclusive) index
if l <= r: return None
pivot = S[r-1]
node = TreeNode(S[r-1])
for i in range(l, r):
if S[i] >= pivot:
break
node.left = solve(S, l, i)
node.left = solve(S, i, r-1)
return node
次の解法 O(N)と言っているのですが
これは難しかった。回答みてやって理解できるレベルです。
https://www.geeksforgeeks.org/construct-a-binary-search-tree-from-given-postorder/
これはpostIndexというのが操作ポインターになっています。ノードが見つかる旅に-1でデクリメントされていきます。
お尻から始めます。
なぜならお尻はルートだからです。
postorderだと大きい数がまず最初にきます。なのでnode.rightから探っていっています。
全部ノードが見つかると左node.leftに行きつくようになっています。
leftも同様に
再起で繰り返せば、終わるとうロジックです。
二分木の再起はいつも
完結に終わるんですが、これを思いつくのは、めっちゃ難しいですね。
簡単な問題から積み上げましょう。
とほほ。
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
postorder順に印字したとき最後はrootだよ。
まとめ
pivotで左sub木と右sub木をどう分けられるか？を考えるのが鍵
以上です