这个问题来自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 回答
树不一定是满的 - 所以它可以有O(n)深度 . 据我所知,空间复杂度为O(n) .
你是对的;当树 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)
时,堆栈帧将如下所示:最远的
depth()
可以递归是树的深度,因此这里的堆栈使用是O(d) .接下来,
depth()
结束,我们称之为递归findSum(TreeNode, int, int[], int)
.这个函数没有分配任何新的内存,它就像
depth()
一样递归到树的深度,因此这里的堆栈使用也是O(d) .因此,该算法中任何时候的最大堆栈使用量为O(d),加上分配的数组使用的O(d)空间,给出了O(d)的最终答案,即O(n)一般情况,如果树是 balancer 的,则为O(log n) .