原题
有两个不同大小的二进制树： T1 有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。
样例
下面的例子中 T2 是 T1 的子树：
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4
下面的例子中 T2 不是 T1 的子树：
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4
解题思路
- 写一个前序遍历，将二叉树扁平化为string
- 判断string1是不是string2的子串
完整代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
# @param T1, T2: The roots of binary tree.
# @return: True if T2 is a subtree of T1, or false.
def isSubtree(self, T1, T2):
# write your code here
res = []
self.get(T1, res)
s1 = "".join(res)
res = []
self.get(T2, res)
s2 = "".join(res)
return s2 in s1
def get(self, root, res):
if root is None:
res.append("#")
return
res.append(str(root.val))
self.get(root.left, res)
self.get(root.right, res)
