如何计算二进制SubTree查找的空间复杂度

Question

这个问题来自于“破解编码采访”一书。我很难理解解决方案的空间复杂性。

问题：

您有两个非常大的二叉树: T1 (数百万节点)和T2 (数百个节点)。创建一个算法来确定T2是否是T1的子树。

解决方案(用Java):

public static boolean containsTree(TreeNode t1, TreeNode t2) {
    if (t2 == null)
        return true; // The empty tree is a subtree of every tree.
    else
        return subTree(t1, t2);
}

/* Checks if the binary tree rooted at r1 contains the binary tree 
 * rooted at r2 as a subtree somewhere within it.
 */
public static boolean subTree(TreeNode r1, TreeNode r2) {
    if (r1 == null)
        return false; // big tree empty & subtree still not found.
    if (r1.data == r2.data) {
        if (matchTree(r1,r2)) return true;
    }
    return (subTree(r1.left, r2) || subTree(r1.right, r2)); 
}

/* Checks if the binary tree rooted at r1 contains the 
 * binary tree rooted at r2 as a subtree starting at r1.
 */
public static boolean matchTree(TreeNode r1, TreeNode r2) {
    if (r2 == null && r1 == null) 
        return true; // nothing left in the subtree
    if (r1 == null || r2 == null) 
        return false; //  big tree empty & subtree still not found
    if (r1.data != r2.data) 
        return false;  // data doesn’t match
    return (matchTree(r1.left, r2.left) && 
            matchTree(r1.right, r2.right));
}

书中说，这个解决方案的空间复杂度是O(log(n) +log(m))，其中m是T1 (大树)中的节点数和T2中的n个节点数。

在我看来，似乎解决方案具有O( log(m) * log(n) )空间复杂性，因为“子树”函数具有log(N)递归调用，并且每个递归调用执行触发log(M)递归调用的"matchTree“函数。

为什么这个解决方案O(log(n) + log(m))的复杂性？

Answer 1

由于我们没有在堆上创建任何对象，空间复杂性就是堆栈的大小。所以问题不是总调用发生了多少次，而是堆栈可以增长多大。

containsTree()只能调用subTree()，subTree()可以调用自己或matchTree()，而matchTree()只能调用自己。因此，在调用matchTree()的任何地方，堆栈看起来都是这样的：

[containsTree] [subTree] ... [subTree] [matchTree] ... [matchTree]

这就是为什么在这里不增加空间复杂性的原因:每次对subTree()的调用都可以调用matchTree()，而对matchTree()的调用在subTree()继续递归之前离开堆栈。

按照“正确答案”的思路进行分析

如果问题没有具体说明树木是否平衡，那么一个真正最坏的分析就会认为它们可能不是。然而，你和这本书都是假设的。我们可以说T1的深度是c，T2的深度是d. c是O(log(m))，如果T1是平衡的，则可以把这个问题留到后面，而O(m)则不然。T2的d也是一样的。

对matchTree()来说，最坏的情况是O(d)，因为它能恢复的最远是T2的高度。

对于subTree()来说，最坏的情况是它的递归是O(c)，因为它所能恢复的最大的是T1的高度，加上调用matchTree()的成本，总共是O(c+d)。

containsTree()只是在调用subTree()的基础上添加了一个常量，所以这不会改变空间复杂性。

因此，如果T1和T2都是平衡的，通过替换c和d，您可以看到O(log(m)+log(n))似乎是合理的。

关于“正确答案”的问题

就像我之前说过的，假设二叉树是平衡的，这是不对的，除非你知道它们是平衡的。因此，更好的答案可能是O(m+n)。

但是等等！问题是T2的大小小于T1的大小。这意味着n是O(m)，log(n)是O(log(m))。所以我们为什么要浪费时间去担心

如果树是平衡的，空间复杂度就是O(log(m))。在一般情况下，你不知道什么是平衡的，真正的答案应该是O(m)，大树的大小。