いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 236 Lowest Common Ancestor of a Binary Tree

投稿日:

こんにちは

今回の学びは

・lcaは暗記レベルで。

 

問題はlowest-common-ancestor-of-a-binary-tree

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

Q:ノードのvalはduplicateする?

Q:同じノードがp,qだったら?

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

O(N)とsO(N)で。

preoderのdfsでいくと、かならずleftとrightからの返却があって、そこで判断します。

dfsはnodeがp,qだったらtrue返す、という単純なもの

最初はグローバル変数で。

 

4、実装しましょう。

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

 

5、エッジケースとサンプルテストを忘れずに!

グローバル変数を使っている点と、見つかった時点で終了する

という工夫を追加したいです。

グローバル変数をつかわずにもっと単純化できます。

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/494746/Easy-understand-DFS-Python-solution

のような感じです。

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は暗記レベルで。

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.