判断B是否为A的子树

发表于 | 分类于 |
判断二叉树B是否为二叉树A的子树

任务描述：对于两棵彼此独立的二叉树A和B，请编写算法，检查A中是否存在一颗子树与B树的拓扑结构完全相同。给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。

思路：可以先将二叉树A与二叉树B序列化，转化为字符串，若树B是树A的子树的话B序列化后的字符串则是A字符串的子字符串。python中的in语法可以方便做到这一点。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class IdenticalTree:
    def chkIdentical(self, A, B):
        # write code here
        StringA = self.serialize(A)
        StringB = self.serialize(B)
        if StringB in StringA:
            return True
        else:
            return False

    def serialize(self, tree):
        if tree is None:
            return "#"
        serial = str(tree.val)
        serial += self.serialize(tree.left)
        serial += self.serialize(tree.right)
        return serial