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

Question

这个问题来自Cracking the Coding Interview一书，我无法理解为他们的解决方案指定的空间复杂度。

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

解决方案(在 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();
}

我的问题:根据解，这个解的空间复杂度是O(n*log(n))。但是，我觉得空间复杂度应该是 O(log(n))，它表示 findSum() 函数的递归堆栈深度。为什么我的分析是错误的？为什么空间复杂度是O(n*log(n))？

Answer 1

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