题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

样例

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}返回True

---

想法一：

使用先序遍历生成两棵树的序列，之后只需要判断序列是否存在即可。

class Solution:    def __init__(self):        self.Root1_list = []        self.Root2_list = []    # 先序遍历    def Createtreelist(self, root, note):        if root is None:            return        if note is True:            self.Root1_list.append(root.val)            self.Createtreelist(root.left, True)            self.Createtreelist(root.right, True)        else:            self.Root2_list.append(root.val)            self.Createtreelist(root.left, False)            self.Createtreelist(root.right, False)    def HasSubtree(self, pRoot1, pRoot2):        """        :param pRoot1: TreeNode        :param pRoot2: TreeNode        :return:        """        self.Createtreelist(pRoot1, True)        self.Createtreelist(pRoot2, False)        p = self.Root2_list        q = self.Root1_list        # 如果为空树直接返回 false        if len(p) is 0:            return False        note2 = 0        for i in range(len(q)):            if note2 == len(p):                break            if q[i] == p[note2]:                note2 += 1            else:                if q[i] == p[0]:                    continue                note2 = 0        if note2 == len(p):            return True        return False

想法二：

通过百度得来的，递归查找，对于递归还是运用的不是很熟练:-)

class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass Solution:    def SearchSimiler(self, p1, p2):        # B树为空，则存在        if p2 is None:            return True        if p1 is None:            return p1 == p2        flag = False        if p1.val == p2.val:            # 查找该节点的左右节点            flag = self.SearchSimiler(p1.left, p2.left) and self.SearchSimiler(p1.right, p2.right)        # 如果flag为True，返回True，否则继续从左节点开始查找，如果还失败，从右节点开始查找        return flag or self.SearchSimiler(p1.left, p2) or self.SearchSimiler(p1.right, p2)    def HasSubtree(self, pRoot1, pRoot2):        """        :param pRoot1: TreeNode        :param pRoot2: TreeNode        :return:        """        # write code here        if pRoot1 is None or pRoot2 is None:            return False        return self.SearchSimiler(pRoot1, pRoot2)

---

最后

刷过的LeetCode源码或剑指offer放在上了，希望喜欢或者觉得有用的朋友点个star或者follow。

有任何问题可以在下面评论或者通过私信或联系方式找我。

联系方式

QQ：791034063

Wechat：liuyuhang791034063

CSDN：

Github：