问对于不平衡树的所有路径和问题，最坏的空间复杂度是多少？

EN

下面是在educative.io上所述的问题陈述。

给出一棵二叉树和一个数字‘S’，找出从根到叶的所有路径，使得每个路径的所有节点值之和等于‘S’。

我理解这个问题的解决方案和时间复杂性部分。我的困惑在于最糟糕的空间复杂性。对于平衡二叉树，计算了输出数组的空间复杂度，得出了不平衡二叉树的空间复杂度相同的结论。

这里有七个节点(即N= 7)。因为对于二叉树来说，只有一条路可以到达任何一个叶节点，所以我们可以很容易地说，二叉树中的总根到叶路径不能超过叶子的数量。正如我们所知道的，二叉树中不可能有超过(N+1)/2的叶子，因此allPaths中元素的最大数量将是O((N+1)/2) = O(N)。现在，这些路径中的每一条都可以有许多节点。对于平衡的二叉树(如上面所示)，每个叶节点都将处于最大深度。众所周知，平衡二叉树的深度(或高度)是O( logN )，我们最多可以说，每条路径中都有logN节点。这意味着allPaths列表的总大小为O(N*logN)。如果树不平衡，我们仍然会有同样的最坏的空间复杂性。

通过上述讨论，我们可以得出，我们的算法的总体空间复杂度为O(N*logN)。

此外，根据上述讨论，因为对于每个叶节点，在最坏的情况下，我们必须复制log(N)节点来存储它的路径，因此算法的时间复杂度也将是O(N*logN)。

我画了几棵7，8，9的二叉树，.节点和我能够创建不平衡的树，这将需要更多的空间在输出数组比它的平衡树对应。此外，这种差异并不是由一个恒定的值增长的。