Space 2 个二叉树的 isSubtree 函数的复杂度

Question

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        return areSame(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean areSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null || subRoot == null) return false;
        if (subRoot.val != root.val)
            return false;
        return areSame(root.left, subRoot.left) && areSame(root.right, subRoot.right);
    }

我上面的解决方案的 space 复杂性是为了找到另一棵二叉树的树 is subtree - O(height(tree1)) （如大多数讨论评论中所建议的那样）或O(高度(树1)+高度(树2)) 其中

我认为它应该是 O(height(tree1) + height(tree2)) 因为 isSubtree 可以深入到 tree1 的一个分支，并且对于每次调用， isSame() 可以作为深度为 height(tree2)，因此在任何时刻使用的最大堆栈内存将为 ht1+ht2。

Answer 1

假设布尔运算符 && 和 || 是 short-circuiting 运算符（因为它们在 Java 中），递归深度（和额外的堆栈内存）是上限为 O(height(tree1)).

因为isSubtree(root, subRoot)只能调用自己（第一棵树的高度减1）或areSame(root, subRoot)，并且最多直接调用'areSame'一次'isSubtree'一次可以入栈（因为short-circuiting），递归深度为O(height(tree1)) + max-depth-of(areSame(tree1, tree2)).

现在，如果 root 为空，areSame(root, subRoot) 将不会进行递归调用。如果 root 不为空，它可能会调用：

areSame(root.left, subRoot.left) && areSame(root.right, subRoot.right);

这里，它调用areSame只用root的子节点：第一棵树的高度已经减少了1，并且第一次调用必须在第二次调用开始之前完成（因为&& short-circuits)。因此在任何时候最多可以 height(tree1) + 1 调用 call-stack 上的 areSame，因此 isSubtree 的总递归深度/堆栈 space 是 O(height(tree1))

Space 2 个二叉树的 isSubtree 函数的复杂度

Space complexity of isSubtree function for 2 binary trees

algorithm

recursion

complexity-theory

binary-tree