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

这个问题来自《破解编码面试》一书，我很难理解为其解决方案指定的空间复杂性。

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

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

最佳答案

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