解题思路

单递归：先判断pRoot1和pRoot2如果不相等的话，递归调用使pRoot1的左结点和右结点分别与pRoot2比较，两者的返回结果任意一个为True即可。如果pRoot1和pRoot2相等，就再次判断pRoot2是否左右子结点都为空，（1）如果都为空，则说明此时pRoot2已经都比较过了，直接返回True；（2）如果都不为空，那么递归调用使pRoot1左结点与pRoot2左结点、pRoot1右结点与pRoot2右结点比较（这两者的返回结果要同时为True，设为result1），或者pRoot1的左结点和右结点分别再与pRoot2比较（设结果为result2、result3），那么这三个结果满足其一即可，即result1 or result2 or result3；（3）如果pRoot2左结点为空，那么需要比较pRoot1和pRoot2的右结点；（4）如果pRoot2右结点为空，那么需要比较pRoot1和pRoot2的左结点。（文字描述比较麻烦，结合代码看）
双递归：定义一个新方法func2(root1, root2)用来判断root2是否等于root1并且是其子树，具体方法是先判断root2是否为空，如果为空说明root2已经比较完了，直接返回True。再判断root1是否为空，此时root2已经确定非空，如果root1为空的话说明root1和root2已经有了差异，直接返回False。然后比较root1和root2是否相等，如果相等的话，递归调用比较root1的左结点与root2的左结点、root1的右结点与root2的右结点，两者的比较结果要同时为True；如果root1和root2不相等，直接返回False。在原方法中，先调用func2方法判断此时pRoot2是否等于pRoot1并且是它的子树，如果不满足，则递归调用原方法，再次使pRoot1的左结点和右结点分别与pRoot2比较，两者结果任意满足其一即可。（这个方法相当于把方法一的递归拆成了两部分，更容易理解）

实现

python

单递归：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        if pRoot1.val != pRoot2.val:
            return self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
        elif not pRoot2.left and not pRoot2.right:
            return True
        elif pRoot2.left and pRoot2.right:
            return (self.HasSubtree(pRoot1.left, pRoot2.left) and self.HasSubtree(pRoot1.right, pRoot2.right)) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
        elif not pRoot2.right:
            return self.HasSubtree(pRoot1.left, pRoot2.left)
        else:
            return self.HasSubtree(pRoot1.right, pRoot2.right)

python

双递归：

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if not pRoot1 or not pRoot2:
            return False
        if self.isTree2in1(pRoot1, pRoot2):
            return True
        else:
            return self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)


    def isTree2in1(self, pRoot1, pRoot2):
        if not pRoot2:
            return True
        if not pRoot1:
            return False
        if pRoot1.val == pRoot2.val:
            return self.isTree2in1(pRoot1.left, pRoot2.left) and self.isTree2in1(pRoot1.right, pRoot2.right)
        else:
            return False