题目

难度：★☆☆☆☆
类型：二叉树

给定两个非空二叉树 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))

如有疑问或建议，欢迎评论区留言~