algorithm - 不平衡树的所有路径和问题的最坏情况空间复杂度是多少？

Question

这是 educative.io 上所述的问题陈述。

Given a binary tree and a number ‘S’, find all paths from root-to-leaf such that the sum of all the node values of each path equals ‘S’.

我理解问题的解决方案和时间复杂度部分。我的困惑在于最坏情况下的空间复杂度。输出数组的空间复杂度是针对平衡二叉树计算的，结论是对于非平衡二叉树也是一样的，没有任何解释。

Here we have seven nodes (i.e., N = 7). Since, for binary trees, thereexists only one path to reach any leaf node, we can easily say thattotal root-to-leaf paths in a binary tree can’t be more than thenumber of leaves. As we know that there can’t be more than (N+1)/2leaves in a binary tree, therefore the maximum number of elements inallPaths will be O((N+1)/2) = O(N). Now, each of these paths can havemany nodes in them. For a balanced binary tree (like above), each leafnode will be at maximum depth. As we know that the depth (or height)of a balanced binary tree is O(logN) we can say that, at the most,each path can have logN nodes in it. This means that the total size ofthe allPaths list will be O(N*logN). If the tree is not balanced, wewill still have the same worst-case space complexity.

From the above discussion, we can conclude that our algorithm’soverall space complexity is O(N*logN).

Also, from the above discussion, since for each leaf node, in theworst case, we have to copy log(N) nodes to store its path; therefore,the time complexity of our algorithm will also be O(N*logN).

我绘制了几个具有 7、8、9 ... 节点的二叉树，并且我能够创建不平衡树，与平衡树对应物相比，它们在输出数组中需要更多空间。此外，差异不会以恒定值增长。

Answer 1

对你有好处，实际上是仔细检查推理而不是相信它是正确的!

平衡二叉树的分析方法对于不平衡二叉树也是正确的。但是不平衡的深度可以是 O(N)。因此，最大空间是路径数乘以深度，即 O(N) * O(N) = O(N^2)。

对于达到最坏情况的不平衡二叉树，我们将创建一棵树，所有这些节点的值都为 1，大小为 2 的幂。前半部分节点是一条向右延伸的直线。另一半是上半场结束时的完美平衡二叉树。这棵树将有 O(N/4) 个权重为 N/2 + log_2(N/2) 的路径，并且确实需要 O(N^2) 空格。

我强烈建议向他们指出错误，以便他们改正。