不平衡树的所有路径和问题的最坏情况 space 复杂度是多少？
What's the worst-case space complexity for the All Paths Sum problem for an unbalanced tree?
这是 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’.
我理解问题的解决方案和时间复杂度部分。我的困惑在于最坏情况 space 的复杂性。 space 输出数组的复杂度是针对平衡二叉树计算的，结论是它与不平衡二叉树相同，没有任何解释。
Here we have seven nodes (i.e., N = 7). Since, for binary trees, there
exists only one path to reach any leaf node, we can easily say that
total root-to-leaf paths in a binary tree can’t be more than the
number of leaves. As we know that there can’t be more than (N+1)/2
leaves in a binary tree, therefore the maximum number of elements in
allPaths will be O((N+1)/2) = O(N). Now, each of these paths can have
many nodes in them. For a balanced binary tree (like above), each leaf
node 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 of
the allPaths list will be O(N*logN). If the tree is not balanced, we
will still have the same worst-case space complexity.
From the above discussion, we can conclude that our algorithm’s
overall space complexity is O(N*logN).
Also, from the above discussion, since for each leaf node, in the
worst 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 ... 节点的二叉树，并且我能够创建不平衡树，这些树在输出数组中需要比平衡树更多 space对方。此外，差异不会以恒定值增长。
对你有好处，实际上是仔细检查推理而不是相信它是正确的！
平衡二叉树的分析方法对于不平衡二叉树也是正确的。但是不平衡的可以有深度O(N)。因此，最大值 space 是路径数乘以深度，即 O(N) * O(N) = O(N^2).
对于达到最坏情况的不平衡二叉树，我们将创建一棵树，所有这些节点的值为1，大小为2的幂。前半部分节点是一条向右延伸的直线。另一半是上半场结束时的完美平衡二叉树。这棵树将有 O(N/4) 条权重为 N/2 + log_2(N/2) 的路径，并且确实需要 O(N^2) space.
我强烈建议向他们指出错误，以便他们改正。
这是 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’.
我理解问题的解决方案和时间复杂度部分。我的困惑在于最坏情况 space 的复杂性。 space 输出数组的复杂度是针对平衡二叉树计算的，结论是它与不平衡二叉树相同，没有任何解释。
Here we have seven nodes (i.e., N = 7). Since, for binary trees, there exists only one path to reach any leaf node, we can easily say that total root-to-leaf paths in a binary tree can’t be more than the number of leaves. As we know that there can’t be more than (N+1)/2 leaves in a binary tree, therefore the maximum number of elements in allPaths will be O((N+1)/2) = O(N). Now, each of these paths can have many nodes in them. For a balanced binary tree (like above), each leaf node 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 of the allPaths list will be O(N*logN). If the tree is not balanced, we will still have the same worst-case space complexity.
From the above discussion, we can conclude that our algorithm’s overall space complexity is O(N*logN).
Also, from the above discussion, since for each leaf node, in the worst 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 ... 节点的二叉树，并且我能够创建不平衡树，这些树在输出数组中需要比平衡树更多 space对方。此外，差异不会以恒定值增长。
对你有好处，实际上是仔细检查推理而不是相信它是正确的！
平衡二叉树的分析方法对于不平衡二叉树也是正确的。但是不平衡的可以有深度O(N)。因此，最大值 space 是路径数乘以深度，即 O(N) * O(N) = O(N^2).
对于达到最坏情况的不平衡二叉树，我们将创建一棵树，所有这些节点的值为1，大小为2的幂。前半部分节点是一条向右延伸的直线。另一半是上半场结束时的完美平衡二叉树。这棵树将有 O(N/4) 条权重为 N/2 + log_2(N/2) 的路径，并且确实需要 O(N^2) space.
我强烈建议向他们指出错误，以便他们改正。