こんにちは
今回の学びは
・inorderの読み順の特徴をとらえることですinorderの読み順の特徴をとらえることです
・各要素の特徴を考えて、それらを利用できないかと考える。
・発想が乏しい→もっと多くのパターンに触れる
・（お試し中仮説）デグレが数回は発生する場合はアイデアを見直した方が良い
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
preorderでの読み順と
inorderでの読み順と
二つ渡されるんで、そこから元の木を作ってください
これは非常に面白い問題です。
最初、そんなことできるの？って
感じでした。
手が出ない時は、つまり、パッと解法が思いつかない時は
サンプルでいくつか自分で試してみて、書き出したら声に出したり
パターンをつかもうとします。
20分考えましたが、この問題に関しては
少し惜しいところまでったかもしれませんが、解けませんでした。
簡単なケースでのみ通るこじつけロジックで終わってしまいました。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
O(n)です。ロジックは無着ですが。。。
いくつかサンプルを書き出して、言って
パターンが見えてこないか頑張ること1時間くらい言ったと思いますが、全然ですが
答えを見ることにしました
この問題のきもは
inorderの読み順の特徴をとらえることです
例えば
3
/ \
2 4
/ \
15 20
っていう木を見てください
これはinorder表記すると
2, 3, 15, 4, 20
になります。
この表記の特徴は、読み方の特徴と言い換えてもいいかもしれません。
inorderはまず、左を読み、そして 真ん中を読み、最後に右を読みます
大きくとらえると、まず左subtreeを読み、そしてrootノードを読み、最後に右subtreeを読みます。
つまり
・真ん中がわかれば、その左の読み順は全て左subtreeの要素です。
上の例だと3が真ん中ですので、その左側が全部左subtreeです、と言っても[2]しかないですが、
で、同様に3のその右側が全部右subtreeです。[15, 4, 20]です
これが一つの特徴です。他にもあるかもしれませんが、この問題を解くのにはこの特徴が最大の
特徴でかつうまく活かしたい特徴でした。
私はこれには全く気付きませんでした。
さて
この特徴が見えたならば、なんか使えそう。っと風に考えてみるもです
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
3
/ \
9 20
/ \
15 7
preorderの方の特徴は？
・先頭はルートノードである。真ん中のノードである。
・最後は一番右はしのノードである
と言った感じでしょうか。
ここで二つの特徴を融合させられれば
この問題は解けます。
先頭の（真ん中）ノードはわかり、真ん中が分かれば、その左と右subtreeもわかる。
つまり
・各要素の特徴を考えて、それらを利用できないかと考える。
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
が与えられたら
真ん中と右と左を言い当てる関数を作ります。
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
def rec(preorder, inorder)
center = 真ん中はこれだ！！
center.left = 左subtreeはこいつらだ！を利用して次の rec()
center.right = 右subtreeはこいつらだ！を利用して次の rec()
return 真ん中はこれだ！！
この問いの工夫はpreorderは真ん中軍と読み替えてもいいかもしれない。
この真ん中軍は一個づづpopしていく。だった、もう真ん中ってわかったら取り出していいでしょ
そして
新たなsubtreeにも、また真ん中は必ず存在する！ （これもまた特徴ですな）
これが今回の
テクニックの全説明だ
自分では思いつきませんでしたが、正解を元に書いた動く実装はこちら
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if preorder is None or inorder is None: return None
if len(preorder) == 0 or len(inorder) == 0: return None
node = TreeNode(preorder.pop(0))
rootIdx = inorder.index(node.val)
inorder_left = inorder[:rootIdx]
inorder_right = inorder[rootIdx+1:]
node.left = self.buildTree(preorder, inorder_left)
node.right = self.buildTree(preorder, inorder_right)
return node
ちなみに、最初のぼつ案はこちら。
ある特定のパターンで右と左をわかることができるかと、勘違いして実装し始め、見事
ドツボにハマりました。！w
最後までプランが見えていないと、途中で詰むことが多いです。タチの悪いのは詰んでいるか
詰んでいないのか、方向性は合っているのかが
やっている本人、わからないということ。
今回の私の例で言えば、あのままやっていても正解にはたどり着けなかったので、
首が回らなくなったら、バグを３回くらい直した時にデグレが数回発生するようあケースは
アイデアのロジックに限界があるように思います。
アイデアの方向性がいい場合は、テストケースで詰まっても、それを取り除けば、また別のテストケースでつまずくことは合っても、デグレは起こさないからです。
・（お試し中仮説）デグレが数回は発生する場合はアイデアを見直した方が良い
# ボツ案です
class Solution_not_enough_idea:
def rec_lefty(self, i, j, P: List[int], I: List[int]) -> TreeNode:
if i >= len(P): return None
if j <= i: return None # invalid i, j relation
value = P[i]
node = TreeNode(value)
node.left = self.rec_lefty(i+1, j, P, I)
return node
def rec(self, i, j, P: List[int], I: List[int]) -> TreeNode:
# i start, j is end(exclusive)
if i >= len(P): return None
if j <= i: return None # invalid i, j relation
value = P[i]
node = TreeNode(value)
# find
for k in range(i, j):
if I[k] == value: break
if k < j: # 見つかった
node.left = self.rec_lefty(i+1, k+1, P, I)
node.right = self.rec(k+1, j, P, I)
else: # 見つかってない
#node.left = self.rec(i+1, j, P, I)
node.left = self.rec_lefty(i+1, j, P, I)
return node
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
return self.rec(0, len(preorder), preorder, inorder)
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
自力でパターン見つからず。
一時間以上は、考えたかと思います。
なぜ、一時間考えても見つからないのでしょうか？
探すパターンが少ない
探すスピードが遅い
探す範囲が右往左往している。ちゃんと終わったものには済みとかつけないと二度手間。->-チェックリストをつける
--> フレームワークで優先づけて、作る
発想が乏しい→もっと多くのパターンに触れる
ということで
手探りに状態の時に答えが見つかるのは稀。
ここで覚えたいのは
inorderの場合はinorderのとあるポイントの右側は、全て右の木
左側は左に木という
特徴があるよいうことだ！
秀逸やろ！こんなん！すごいわ。
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/371081/Simple-Python-Solution
なんか、ひねり出した感じ。俺の路線はこれだったと思う。
ちゃんと、法則を綺麗に見つけ出しているところがすごい
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/373804/Iterative-Python-solution
まとめ
・inorderの読み順の特徴をとらえることですinorderの読み順の特徴をとらえることです
・各要素の特徴を考えて、それらを利用できないかと考える。
・発想が乏しい→もっと多くのパターンに触れる
・（お試し中仮説）デグレが数回は発生する場合はアイデアを見直した方が良い
以上です