【题目描述】
输入两棵二叉树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)
