算法思想一：递归

解题思路：

1.这道题判断是否是子结构，主要看pRoot2和pRoot1的根节点的值是否一样，一样的话再同时递归，
2.判断left节点，如果pRoot2的左节点为null,则说明pRoot2的left节点满足条件。
3.若pRoot2的节点不为null,并且pRoot1的left节点为null,或者说它们二者的值不一样，说明pRoot2不是pRoot1的子结构。
4.pRoot1和pRoot2的right节点和第2.3步一样的判断，当left和right同时成立，pRoot2才是pRoot1的子结构
5.因为题目约定空树不是任意一个数的子结构，所以pRoot1和pRoot2都不能为空，这是返回true的前提条件

代码展示：

Python版本 
class Solution:
    def doesTree1HasTree2(self, pRoot1, pRoot2):
        if pRoot2 == None:
            return True
        if pRoot1 == None:
            return False
        if pRoot1.val !=pRoot2.val:
            return False
        return self.doesTree1HasTree2(pRoot1.left,pRoot2.left) and self.doesTree1HasTree2(pRoot1.right, pRoot2.right)
         
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot1 ==None　or pRoot2==None:
            return False
        return self.doesTree1HasTree2(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)

复杂度分析：

时间复杂度O(MN)：其中 M,N分别为树 pRoot1和 树 pRoot2的节点数量；先序遍历树pRoot1 占用 O(M)，每次调用 dfs(A, B) 判断占用 O(N)。
空间复杂度O(M)：当树 pRoot1 和树 pRoot2 都退化为链表时，递归调用深度最大。当 M≤N 时，遍历树pRoot1 与递归判断的总递归深度为 M ；当 M>N 时，最差情况为遍历至树pRoot1叶子节点，此时总递归深度为 M。

算法思路二：非递归

解题思路：

1.先遍历树pRoot1，如果遍历到和pRoot2节点值相同的节点，进入isSubTree方法判断接下来的节点是否都相同
2.节点都相同返回True；不相同返回False，并且继续遍历树pRoot1找下一个相同的节点
3.如果遍历完了pRoot1还没有返回过True，说明pRoot2不是pRoot1的子结构，返回False
isSubTree方法：用于判断从pRoot1的子树是否有和pRoot2相同的部分
1.采用递归的思想，如果节点root1与root2的节点不同，则说明pRoot1的子树与pRoot2不具有相同的节点
2.如果值相同，则递归判断（isSubTree）他们各自得左右节点的值是不是相同
3.递归的终止条件时到达pRoot1或pRoot2的叶节点

代码展示：

Python 版本 
class Solution:
    def isSubTree(self, tree1, tree2):
        if tree2 == None:
            return True
        if tree1 == None and tree2!=None:
            return False
        if tree1.val == tree2.val:
            return self.isSubTree(tree1.left, tree2.left) and self.isSubTree(tree1.right, tree2.right)
        else:
            return False
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot2 == None:
            return False
        if pRoot1 == None and pRoot2!=None:
            return False
        flag = False
        if pRoot1.val == pRoot2.val:
            flag = self.isSubTree(pRoot1,pRoot2)
        if not flag:
            flag = self.HasSubtree(pRoot1.left, pRoot2)
            if not flag:
                flag = self.HasSubtree(pRoot1.right, pRoot2)
        return flag

参考资料：