2019-08-23 剑指 树的子结构

40min，自信满满。。。

class Solution:
    def HasSubtree(self, pRoot1:TreeNode, pRoot2:TreeNode):
        if not pRoot2 or not pRoot1:return False
        # if pRoot2.val==pRoot1.val:
        #     if self.isSame(pRoot1,pRoot2):return True
        # else:  # 看了半天答案和别人一样，最终发现是这里else的错误。如果第一个节点一样，那就不会再往下判断了。。。
        #     if self.HasSubtree(pRoot1.left,pRoot2):return True
        #     if self.HasSubtree(pRoot1.right,pRoot2):return True
        # return False
        return self.isSame(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left,pRoot2) or self.HasSubtree(pRoot1.right,pRoot2)

    def isSame(self,parent:TreeNode,child:TreeNode): #这里注意parent会比child大
        if not child:return True# if not parent and not child:return True 
        if not parent:return False# if not parent or not child:return False
        if parent.val!=child.val:return False
        return self.isSame(parent.left,child.left) and self.isSame(parent.right,child.right)