NeetCodeのSolutionを書いていく #
Same Binary Tree #
https://neetcode.io/problems/same-binary-tree
neetcode.io
2つの２分木のルートが与えられます。 木が同じであればtrueをそうでない場合はfalseを返す。 同じ構造で、同じ値を持つ場合に２分木を同一とする。
計算量：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 #
https://neetcode.io/problems/subtree-of-a-binary-tree
neetcode.io
２つのバイナリツリーが与えられる。 １つのルートに内部に他のルートがサブルートとして存在すれば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
いけた。
Reply by Email