首页 文章

如何计算空间复杂度来打印二叉树中给定值求和的所有路径

提问于
浏览
4

这个问题来自Cracking the Coding Interview,我无法理解为其解决方案指定的空间复杂性 .

Problem: 您将获得一个二叉树,其中每个节点都包含一个值 . 设计一种算法来打印总和为给定值的所有路径 . 请注意,路径可以在树中的任何位置开始或结束 .

Solution (in Java):

public static void findSum(TreeNode node, int sum, int[] path, int level) {
    if (node == null) {
        return;
    }

    /* Insert current node into path */
    path[level] = node.data; 

    int t = 0;
    for (int i = level; i >= 0; i--){
        t += path[i];
        if (t == sum) {
            print(path, i, level);
        }
    }

    findSum(node.left, sum, path, level + 1);
    findSum(node.right, sum, path, level + 1);

    /* Remove current node from path. Not strictly necessary, since we would
     * ignore this value, but it's good practice.
     */
    path[level] = Integer.MIN_VALUE; 
}

public static int depth(TreeNode node) {
    if (node == null) {
        return 0;
    } else {
        return 1 + Math.max(depth(node.left), depth(node.right));
    }
}

public static void findSum(TreeNode node, int sum) {
    int depth = depth(node);
    int[] path = new int[depth];
    findSum(node, sum, path, 0);
}

private static void print(int[] path, int start, int end) {
    for (int i = start; i <= end; i++) {
        System.out.print(path[i] + " ");
    }
    System.out.println();
}

My Question: 根据解决方案,此解决方案的空间复杂性为 O(n*log(n)) . 但是,我觉得空间复杂度应该是 O(log(n)) ,它表示 findSum() 函数的递归堆栈深度 . 为什么我的分析错了?为什么空间复杂度 O(n*log(n))

2 回答

  • 0

    树不一定是满的 - 所以它可以有O(n)深度 . 据我所知,空间复杂度为O(n) .

  • 1

    你是对的;当树 balancer 时,该算法的空间复杂度为O(log n) . (请注意,您发布的解决方案是针对与您编写的问题不同的问题 - 它是用于查找 only paths that go down 树 . )也许书中的答案是错误的 . 如果这本书真的没有处理 balancer 或不 balancer 的树木,或者路径可以去的地方,那么错误地写下这个答案,并且没有解释他们如何得出他们的答案......来吧,你应该能够找到更好的本书比研究算法的复杂性 .

    分析

    如果通过说树的深度为d来 balancer 树,我们可以暂时搁置,如果 balancer 则为O(log n),否则为O(n) .

    该算法中有两个使用空间的东西:使用的堆栈空间和分配的数组 . 该 int[] 对象的大小为 depth(node) ,并且在对 findSum(TreeNode, int) 的单次调用中仅分配一次,因此其空间使用量为O(d) .

    findSum(TreeNode, int) 调用 depth(node) 时,堆栈帧将如下所示:

    [findSum(TreeNode, int)] [depth] ... [depth]
    

    最远的 depth() 可以递归是树的深度,因此这里的堆栈使用是O(d) .

    接下来, depth() 结束,我们称之为递归 findSum(TreeNode, int, int[], int) .

    这个函数没有分配任何新的内存,它就像 depth() 一样递归到树的深度,因此这里的堆栈使用也是O(d) .

    因此,该算法中任何时候的最大堆栈使用量为O(d),加上分配的数组使用的O(d)空间,给出了O(d)的最终答案,即O(n)一般情况,如果树是 balancer 的,则为O(log n) .

相关问题