另一棵树的子树复杂度分析

Question

在 Leetcode 上，问题 #572 提示用户检查特定树（由其根给出）是否是另一棵树（由其根给出）的子树。下面是解决这个问题的实现：

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def isSameTree(p, q):
            if not p and not q:
                return True
            if not p or not q or p.val != q.val:
                return False
            
            return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
        
        def recurse(root, subRoot):
            if not root:
                return False
            elif isSameTree(root, subRoot):
                return True
        
            return recurse(root.right, subRoot) or recurse(root.left, subRoot)
        
        return recurse(root, subRoot)

实际上，

recurse()

调用将为父树中的每个节点调用一次。在给定的调用期间，

iSameTree()

将被称为尝试将子树“叠加”到树上，从当前节点开始。如果它能够成功匹配子树的所有组件，那么

iSameTree()

将返回

True

。否则，它将返回

False

。

虽然实现是一种蛮力形式，但我很难讨论时间和空间复杂性。为了分析的目的，我们假设节点中潜在父树的大小由

N

给出，而节点中潜在子树的大小由

M

给出。

说到时间复杂度，我们可以很快得出结论，将会有

N

次对

recurse()

的调用，而 each 有可能生成最多

M

次对

isSameTree()

的调用。因此，最坏的情况下，总共会有

N*M

次调用。除了递归部分之外，每个函数调用都需要恒定的时间来执行，因此我们可以说该算法在最坏情况下是 O(NM)。虽然这是有道理的，但我觉得可能有更严格的界限。换句话说，对于任意的

N

节点父树和

M

节点子树，不可能每一个

N

recurse()

调用都会导致

M

IsSubtree()

调用；例如，叶节点将在第一次

IsSameTree()

调用后自然终止；因此，如果

M

的大小不是 1，则与叶节点关联的

recurse()

调用将导致在所有其他场景中少于 M 次调用。我说这一切是为了问：有没有办法找到更紧的界限？

说到辅助空间复杂度，可能就更复杂了。有些人很快就断言空间复杂度是

O(LogN + LogM)

，但是，这对我来说没有意义。此外，在任何给定时间，调用堆栈上最多可以有

LogN

recurse()

调用。在任何给定时间，我们在调用堆栈上最多可以有

LogM

isSameTree()

调用。虽然这两个陈述都是正确的，但对于任意 N 和

M

来说，它们永远不会“同时”为真。也就是说，要在调用堆栈上实现

LogM

isSameTree()

调用，最近的

recurse()

调用需要位于距父树中的叶节点至少

LogM

层的节点上；因此，节点的最深层次是

LogN - LogM

。由此可见，在给定时间，调用堆栈上只能有

LogN - LogM

recurse()

调用和

LogM

isSameTree

调用；总共有

LogN

次调用。另一方面，为了在调用堆栈上存在

LogN

recurse()

调用，最近对

recurse()

的调用需要位于父树中的叶节点上。在这种情况下，此

recurse()

调用最多只能导致调用堆栈上的 2

IsSubtree()

额外调用。根据这个逻辑，那么，辅助空间就是

O(LogN)

。我说这么多就是想问：辅助空间是

O(LogN)

还是

O(LogN + LogM)

？

Answer 1

最坏情况时间复杂度为 θ(NM)。例如，当 M=N/2 时，您将对尺寸 M 进行 N/2 次比较，NM/2 的单位是 Ω(NM)。

最坏情况的空间复杂度是 θ(N)。你的递归永远不会比深度 N 更深，而且无论 M 是什么，你都会到达深度 N。

您可以通过仅将要查找的子树与相同高度的子树进行比较来制作简单的线性时间算法。