面试18：树的子结构

【题目描述】
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
【思路】
递归，
issubstree(root1,root2)判断root2是否为root1的子树，且根值相等
若当前pRoot1的根节点不等于pRoot2，则分别pRoot1探索左右子树是否存在子树pRoot2。
【代码】

# 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 pRoot1==None or pRoot2 == None:
            return False
        #case1:当前值相等
        res = False
        if pRoot1.val == pRoot2.val:
            #则判断根节点下是不是pRoot2的子树
            res = self.issubstree(pRoot1,pRoot2)
        if res == False:
            #探索左子树
            res = self.HasSubtree(pRoot1.left,pRoot2)
        if res ==False:
            #探索右子树
            res = self.HasSubtree(pRoot1.right,pRoot2)
        return res
    def issubstree(self,root1,root2):
        if root2 == None:
            #说明root2全部匹配成功
            return True
        if root1 == None:
            #搜索完root1，无匹配
            return False
        if root1.val != root2.val:
            #不相等则说明当前子树不相等
            return False
        #当前匹配，需要左右子树都需要匹配
        return self.issubstree(root1.left,root2.left) and self.issubstree(root1.right,root2.right)