LeetCode 572. 另一个树的子树 | Python

572. 另一个树的子树

题目来源：https://leetcode-cn.com/problems/subtree-of-another-tree

题目

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:

给定的树 s:

给定的树 t：

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:

给定的树 s：

给定的树 t：

返回 false。

解题思路

思路：深度优先搜索

在这里，先分析题意：

一个二叉树若为另一个树的子树，则它含有与另外一个树的子树相同结构和节点值。
根据示例 2 可知，判断是否为子树，必须有完全相同结构和节点值。

现在将题意转换为可实现代码书写的思路，判断两个树是否相等，那么下面的条件必须同时成立：

当前两个树根节点值相同；
s 的左子树与 t 的左子树相同；
s 的右子树与 t 的右子树相同。

根据上面的思路，本篇幅考虑使用深度优化搜索的方法，枚举 s 的每个节点，判断这个点的子树是否与 t 相等。使用深度优先搜索检查，从根出发，同步移动遍历两个树，判断相应的位置是否相等。

具体的代码实现如下。

代码实现

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:

        return self.dfs(s, t)

    def dfs(self, c, t):

        # c 子树为空时，返回 False

        if not c:

            return False

        return self.is_same(c, t) or self.dfs(c.left, t) or self.dfs(c.right, t)

    def is_same(self, c, t):

        # 两个树都为空时，也认为是相同

        if (not c) and (not t):

            return True

        # 当其中一个树为空，但另外一个树不为空时，此时则为不同

        if (not c and t) or (c and not t):

            return False

        # 两个树都不为空，若值不同，也为不同

        if (c.val != t.val):

            return False

        # 上面的情况都不符合时，继续向下检查

        return self.is_same(c.left, t.left) and self.is_same(c.right, t.right)

实现结果

LeetCode 572. 另一个树的子树 | Python-LMLPHP