LeetCode#572另一棵树的子树算法：时间与空间复杂度疑问

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()函数会遍历父树的每个节点，每次调用时通过isSameTree()尝试将子树与当前节点开始的父树片段匹配，匹配成功则返回True，否则继续遍历。

复杂度分析疑问 #

假设父树节点数为N，子树节点数为M，存在以下两处疑问：

• 时间复杂度：初步判断最坏情况为O(N*M)，但并非每个recurse()调用都会触发M次isSameTree()（如叶节点在M>1时会提前终止），是否存在更紧的时间复杂度边界？
• 空间复杂度：有人认为是O(LogN + LogM)，但我认为递归栈的最大深度实际为O(LogN)，因为两种递归的最大深度不会同时出现，请问正确的辅助空间复杂度是哪一个？

内容的提问来源于stack exchange，提问作者LateGameLank