树的子结构

微信图片_20191227151204.jpg

class Solution:
    def isEqual(self, pRoot1, pRoot2):
        if pRoot2 is None:
            return True
        if pRoot1 is None:
            return False
        if pRoot1.val == pRoot2.val:
            ret1 = self.isEqual(pRoot1.left, pRoot2.left)
            ret2 = self.isEqual(pRoot1.right, pRoot2.right)
        else:
            return False
        return ret1 and ret2
    
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot1 is None or pRoot2 is None:
            return False
        if pRoot1.val == pRoot2.val:
            ret = self.isEqual(pRoot1, pRoot2)
            if ret:
                return True
        ret = self.HasSubtree(pRoot1.left, pRoot2)
        if ret:
            return True
        ret = self.HasSubtree(pRoot1.right, pRoot2)
        return ret