题解 | #树的子结构#
树的子结构
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param pRoot1 TreeNode类 # @param pRoot2 TreeNode类 # @return bool布尔型 # class Solution: # 递归比较 def diguibijiao(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool: if pRoot1 is None and pRoot2 is not None: return False if pRoot2 is None or pRoot2 is None: return True # 判断对应值是否相同,并且左子树和右子树是否相同 return pRoot1.val == pRoot2.val and self.diguibijiao(pRoot1.left,pRoot2.left) and self.diguibijiao(pRoot1.right,pRoot2.right) def HasSubtree(self , pRoot1: TreeNode, pRoot2: TreeNode) -> bool: # write code here if pRoot2 is None: return False if pRoot1 is None and pRoot2 is not None: return False if pRoot1 is None or pRoot2 is None: return True # 递归比较返回值 flag1 = self.diguibijiao(pRoot1,pRoot2) # 上面比较失败,换根结点比较 flag2 = self.HasSubtree(pRoot1.left,pRoot2) flag3 = self.HasSubtree(pRoot1.right,pRoot2) return flag1 or flag2 or flag3#我的实习求职记录#