以下是education .io上的问题陈述。
给定一棵二叉树和一个数字' S '，求出从根到叶的所有路径，使得每条路径的所有节点值之和等于' S '。
我理解问题的解决方案和时间复杂度部分。我的困惑在于最坏情况下的空间复杂度。对于平衡二叉树，我们计算了输出数组的空间复杂度，对于不平衡二叉树，我们得出了相同的结论，没有任何解释。
这里我们有7个节点(即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，…节点和我能够创建不平衡的树，这将需要更多的空间在输出数组比它的平衡树对应。而且，差值不会增加一个常数值。
很好，实际上是仔细检查推理，而不是相信它是正确的!
对于平衡二叉树的分析方法对于不平衡二叉树也是正确的。但是不平衡轨道的深度可以是O(N)。因此，最大空间是路径数乘以深度，也就是O(N) * O(N) = O(N^2)。
对于达到最坏情况的非平衡二叉树，我们将创建一个所有节点的值为1，大小为2的幂的树。前一半的节点是一条通向右边的直线。另一半是前一半结束时的完美平衡二叉树。这棵树将有O(N/4)条权重为N/2 + log_2(N/2)的路径，并且确实需要O(N^2)的空间。
我强烈建议向他们指出错误，以便他们改正。