こんにちは
今回の学びは
・lcaは暗記レベルで。
問題はlowest-common-ancestor-of-a-binary-tree
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
Q:ノードのvalはduplicateする？
Q:同じノードがp,qだったら？
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
O(N)とsO(N)で。
preoderのdfsでいくと、かならずleftとrightからの返却があって、そこで判断します。
dfsはnodeがp,qだったらtrue返す、という単純なもの
最初はグローバル変数で。
４、実装しましょう。
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q:TreeNode) -> TreeNode:
lca = [None]
def dfs(node, p, q):
# looking for p OR q
if node:
ret_m = node.val == p.val or node.val == q.val
ret_l = dfs(node.left, p, q)
ret_r = dfs(node.right, p, q)
if (ret_l and ret_r) or (ret_m and ret_l) or (ret_m and ret_r):
if lca[0] is None:
lca[0] = node
return True
return any([ret_m, ret_l, ret_r])
return False
ans = dfs(root, p, q)
return lca[0] if lca[0] else root
５、エッジケースとサンプルテストを忘れずに！
グローバル変数を使っている点と、見つかった時点で終了する
という工夫を追加したいです。
グローバル変数をつかわずにもっと単純化できます。
のような感じです。
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q:TreeNode) -> TreeNode:
def dfs(node, p, q):# looking for p OR q
if not node or node == p or node == q:
return node
left = dfs(node.left, p, q)
right = dfs(node.right, p, q)
if left and right: return node
return left if left else right
return dfs(root, p, q)
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
lcaは暗記レベルで。
まとめ
・lcaは暗記レベルで。
以上です