【アルゴリズム脳トレ】leetcode easy 572 Subtree of Another Tree

こんにちは

今回の学びは

・

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

はじめて

と直接コーディングにかかりました。

easy　とうことで

解けるだろう

と希望的観測も含めつつ。

ちょっと考えるが結構難しい。

一個づつdfsしていってその地点からsubtreeと同じか？というのを

ひらたすらくりかえす O(s * t)というアルゴリズム。

ブルートフォースにあたるとおもうが、他に思いつかないし

easyだし通るだろうとうことで実装。

実装後です。timespace analysis (時間とスペースの分析）は　◯◯

class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        
        def is_same_tree(a: TreeNode, b: TreeNode):
            if a == None and b == None: return True
            if a is None and b: return False
            if b is None and a: return False
            if a.val == b.val:
                return is_same_tree(a.left, b.left) and is_same_tree(a.right, b.right)
            else:
                return False
            
        def dfs(node: TreeNode):
            if is_same_tree(node, t):
                return True
            if node.left:
                if dfs(node.left): return True
            if node.right:
                if dfs(node.right): return True
            return False
                
        return dfs(s)

コンパクトにかける模様 -> https://leetcode.com/problems/subtree-of-another-tree/discuss/370293/python-recursive-1-function-5-lines

サイズをつかって無駄をなくして、いわゆる枝刈りにあたるのかな。O(2S + T)とのこと。-> https://leetcode.com/problems/subtree-of-another-tree/discuss/367070/Different-approach-incredibly-simple-O(S-%2B-T)-solution.

まとめ

以上です