程序员面试金典 - 面试题 04.10. 检查子树

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。

如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。

示例 1:

• 输入：t1 = [1, 2, 3], t2 = [2]
• 输出：true

示例 2:

• 输入：t1 = [1, null, 2, 4], t2 = [3, 2]
• 输出：false

提示：

• 树的节点数目范围为[0, 20000]。

题目思考

1. 如何判断 T1 的子树和 T2 是否完全相同?

解决方案

思路

• 为了判断 T1 的子树和 T2 是否完全相同, 我们可以额外定义一个方法, 来递归比较当前 T1 和 T2 节点是否满足子树关系
• 然后从 T1 和 T2 的根节点开始调用该方法, 如果当前两棵树完全相同就直接返回 true, 否则就将 T1 移动到其左右子节点位置, 重新与 T2 的根节点比较即可
• 下面代码中有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(MN)
  • 假设 T1 和 T2 的节点数目分别是 M 和 N, 那么最差情况是对于每个 T1 节点, 都要调用一次 match 方法遍历整个 T2 树, 所以时间复杂度是 O(MN)
• 空间复杂度 O(logM)
  • checkSubTree 递归调用则最多使用 O(logM) 递归栈空间, checkSame 递归调用使用 O(log(min(M, N))) 递归栈空间, 所以整体空间复杂度为 O(logM)

代码

class Solution:
    def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool:
        # 额外checkSame检查n1和n2是否完全一样
        if not t1:
            return not t2

        def checkSame(n1, n2):
            if not n1 and not n2:
                # 都达到空节点, 完全一样
                return True
            if not n1 or not n2:
                # 此时说明某个节点是空, 另一个不是, 一定不可能完全一样
                return False
            # 既要当前n1和n2的值相等, 同时各自左右子树部分也要匹配
            return n1.val == n2.val and checkSame(
                n1.left, n2.left) and checkSame(n1.right, n2.right)

        # 要么t1和t2完全匹配, 要么t2属于t1的左或右子树的某一部分
        return checkSame(t1, t2) or self.checkSubTree(
            t1.left, t2) or self.checkSubTree(t1.right, t2)

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊