剑指Offer__17、树的子结构剑指Offer

题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：
其实这道题有了图之后思路就会更清晰：

文章图片

图片来自于博客园凌风1205，具体博客参见reference。
看图之后就会首先捕捉到一点：如果要判断B是A的子结构，那么必须从B的根节点值来与A中节点进行比对。当B的根节点与A树中某个节点相同时，再判断A的节点的左右子树与B的根节点左右子树是否相同。
上面描述了整体的思路，其编码判断分两部分，一部分用来寻找A的某个节点的值是否与B根节点值一样，当寻找到A的某个节点与B的根节点相同时，程序进入另一部分，即判断A的节点左右子树与B的左右子树是否完全相同。两部分对应了程序的两个函数：HasSubtree(self, pRoot1, pRoot2)和isequal(self,proot1,proot2)，前面的函数用来搜寻A中节点是否与B的根节点相同，后面的函数用于判断当在A中找到一个节点与B根节点相同后，它们的左右子树是否完全相同。
Solution：

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 result = False if pRoot1 and pRoot2:#当两棵树不为空时进行搜寻对比，否则直接返回False if pRoot1.val == pRoot2.val:#先判断A的根节点与B的根节点是否相同 result = self.isequal(pRoot1,pRoot2)#如果相同，判断A、B两棵树的左右子树是否相同 if result is False:#如果A的根节点与B的根节点不同时，判断A的左子树与B的根节点是否相同 result = self.HasSubtree(pRoot1.left,pRoot2) if result is False:#如果A的根节点和左子树都与B的根节点不同时，判断A的右子树与B的根节点是否相同 result = self.HasSubtree(pRoot1.right,pRoot2) return result#如果都不相同，返回Falsedef isequal(self,proot1,proot2): #当A的节点与B的根节点相同后，进一步判断AB的左右子树是否相同 if proot2 is None:#如果此时B已经为空，表明B树已经判断完毕，那么说明全部比对完毕，则返回True return True if proot1 is None:#如果A数已经为空了，说明比对不成功，返回False return False if proot1.val != proot2.val:#如果节点的数值不相等，则返回False return False return self.isequal(proot1.left,proot2.left) and self.isequal(proot1.right,proot2.right)#如果上述情况都不符合，那表明AB树没有比对完，但是比对完的部分都相同，那么继续比较它们的左右节点即可

Reference：
【剑指Offer__17、树的子结构】https://www.cnblogs.com/lfeng1205/p/6826026.html