🍣

NeetCode 150 [Trees]:easy 3/3

2025/01/26に公開

NeetCodeのSolutionを書いていく

Same Binary Tree

2つの2分木のルートが与えられます。
木が同じであればtrueをそうでない場合はfalseを返す。
同じ構造で、同じ値を持つ場合に2分木を同一とする。

計算量:O(n)
メモリ:O(n)

順番に比較すればいいんだろうけど、比較できる状態に書き換えればよいか?

class Solution:
    def serialize(self, tree, serialized):
        if hasattr(tree,"val"):
            serialized.append(tree.val)

        if hasattr(tree,"left"):
            self.serialize(tree.left, serialized)
        else:
            serialized.append(None)

        if hasattr(tree,"right"):
            self.serialize(tree.right, serialized)
        else:
            serialized.append(None)

        return serialized

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if (not p) and (not q):
            return True

        serialized_p = self.serialize(p, [])
        serialized_q = self.serialize(q, [])
        return serialized_p == serialized_q

いけた。

Subtree of Another Tree

2つのバイナリツリーが与えられる。
1つのルートに内部に他のルートがサブルートとして存在すればTrue
そうではない場合はFalse

計算量:O(m * n)
メモリ:O(m + n)

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if self.isSameTree(root,subRoot):
            return True

        if hasattr(root,"left") and self.isSubtree(root.left, subRoot):
            return True

        if hasattr(root,"right") and self.isSubtree(root.right, subRoot):
            return True

        return False

いけた。

Discussion