こんにちは
今回の学びは
・方向性はあっているのだが、デバッグに時間がかかる見込みと見たので切り替えた。（時間勝負の時はこれ大事。）
問題はhttps://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると）
同じレベルの数字が２つあった時は小さい方から並べる。
深さの浅い順に並べる。というマイナールールは結構細かい。
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析を付け加えて）
dfsでうまいこと、x軸とy軸ごとにデータを挿入していく。
３，どれでいくか、一緒に決定しましょう。
timespace analysis (時間とスペースの分析）は 〇〇です
O(N)でデータを揃えたあと
アベレージでLogN* Log(LogN) * LogN* Log(LogN) とう微妙なdefaultdictをソートしまくる
ロジックがあったがら、速さは94%と良かった。
４、実装しましょう。
from collections import defaultdict
class Solution:
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
if root is None: return []
res = defaultdict(lambda : defaultdict(list))
def dfs(node: TreeNode, x: int, y: int, res):
if node is None: return
_y = abs(y)
res[x][_y].append(node.val) # _y is abs y is guarateed that 1 direction
dfs(node.left, x - 1, y - 1, res)
dfs(node.right, x + 1, y - 1, res)
dfs(root, 0, 0, res)
# cost of sorted(dict.iteritems())??
ans = []
for x, xaxis in sorted(res.items()):
v_res = []
for y, vertical_ary in sorted(xaxis.items()):
v_res += sorted(vertical_ary)
ans.append(v_res)
return ans
５、エッジケースとサンプルテストを忘れずに！
木がNoneとき何をかえす？前述の細かいルールに従った結果になっているか？
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
defaultdict自体はdictと一緒で速いので、どんどん使えばよい。bisectも使っても良い問題だと思う。
ボツ案に対して見切りが比較的早かったので吉。ボツ案はこちら。
方向性はあっているのだが、デバッグに時間がかかる見込みと見たので切り替えた。（時間勝負の時はこれ大事。）
class Solution_botsu:
"""
複雑過ぎて、デバッグできなかったコード。
"""
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
if root is None: return []
res0, resM, resP = [], [], []
def dfs(node: TreeNode, x: int, y: int, res0, resM, resP):
if node is None: return
# do something with node.val
if x == 0: # I don't have to generate
if len(res0) == 0:
res0.append([node.val])
else:
res0[0].append(node.val)
elif x < 0:
if len(resM) < abs(x):
resM.append([node.val])
else:
resM[abs(x)-1].append(node.val)
else: # x > 0
if len(resP) < abs(x):
resP.append([node.val])
else:
resP[abs(x)-1].append(node.val)
dfs(node.left, x - 1, y - 1, res0, resM, resP)
dfs(node.right, x + 1, y - 1, res0, resM, resP)
dfs(root, 0, 0, res0, resM, resP)
res = []
for vertical in reversed(resM):
res.append(vertical)
for vertical in res0:
res.append(vertical)
for vertical in resP:
res.append(vertical)
return res
まとめ
・方向性はあっているのだが、デバッグに時間がかかる見込みと見たので切り替えた。（時間勝負の時はこれ大事。）
以上です