🍣
NeetCode 150 [Trees]:easy 3/3
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