日野弥生：勉強しよう
LeetCode 572 - 另一棵树的子树
发表于2025年03月10日
递归解题，类似于判断集合是否是子集，把两数是否相同的递归函数写出来，然后判断子树要对根节点的值是否相等进行分类讨论即可。
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if (not p and q) or (not q and p):
return False
if (p and q and p.val != q.val):
return False
if not p and not q:
return True
left = self.isSameTree(p.left if p.left else None, q.left if q.left else None)
right = self.isSameTree(p.right if p.right else None, q.right if q.right else None)
return left and right
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
# 都为空的时候，空树是空树的子树
if not root and not subRoot:
return True
# 主树为空则失败
elif not root and subRoot:
return False
# 按照题干要求，如果子树不包含主树的所有子节点也不符合要求
elif root and not subRoot:
return False
# 根节点不符合则递归找左右子树
if root.val != subRoot.val:
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
else:
# 根节点相同，则判断子树是否完全相同，或者递归子树进行判断
return (self.isSameTree(root.left, subRoot.left) and self.isSameTree(root.right, subRoot.right)) or (self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot))改进后的代码如下：
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not subRoot:
return True
if not root:
return False
if self.isSameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)