题目
难度：★☆☆☆☆
类型：二叉树
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
题目
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
解答
这是树的一个基础题，判断一棵树是否是另一棵的子树，通过前序遍历的结果是否存在包含关系实现。
class Solution:
def isSubtree(self, s, t):
def pre_order(root, res):
"""
获得二叉树的前序遍历结果
:param root: 二叉树根节点
:param res: 结果存储列表
:return:
"""
if root: # 如果当前节点不为空
res.append(str(root.val)) # 添加当前结点的值
pre_order(root.left, res) # 左子树的前序遍历
pre_order(root.right, res) # 右子树的前序遍历
else: # 如果当前结点为空
res.append('#') # 用“#”代替
s_list, t_list = [], [] # 序列化结果存储器
pre_order(s, s_list) # 获取s的前序遍历结果
pre_order(t, t_list) # 获取t的前序遍历结果
# print(','.join(t_list))
# print(','.join(s_list))
# 将列表转为字符串进行比较，前端加“，”防止出现“2,#,#”in“12,#,#”中的情况
return ','+','.join(t_list) in ','+','.join(s_list)
同样，我们可以考虑使用元组精简上述复杂的前序遍历流程：
class Solution:
def isSubtree(self, s, t):
# 这个函数把树序列化为一个元组
toTup = lambda n: (n.val, toTup(n.left), toTup(n.right)) if n else None
# 把元组转化为字符串以方便比较
return str(toTup(t)) in str(toTup(s))
如有疑问或建议，欢迎评论区留言~
