更新： - 维基百科说
o(n)不O(n)所以这个算法不是一个就地解决方案。 - 争论此解决方案是运行在O(n)还是O(1)。
这是我对 LeetCode 问题的解决方案 将二叉树展平到链表.在时间和空间复杂度分析方面，根据一些解释，我不太确定它是否O(1)。我认为这很O(n)，因为使用了堆栈。我的分析正确吗？
根据维基百科，O(n)仍然被接受为就地。
更广泛地说，就地意味着算法不使用额外的空间来操作输入，但可能需要一个小但非恒定的额外空间来操作。通常，这个空格是O(log n)，尽管有时允许o(n)中的任何空间。
/**
* Function flattens a binary tree.
* Time = O(n) because we iterate through all nodes.
* Space = O(n) because we use a stack.
* @param {root} root Input tree.
*/
var flatten = function(root) {
// If reach end of leaf node, return.
if (root === null) return;
let stack = [];
let currentNode = root;
while (true) {
// Push right branch to stack first,
if (currentNode.right) stack.push(currentNode.right);
// then left branch.
if (currentNode.left) stack.push(currentNode.left);
// If there are branches in stack:
if (stack.length > 0) {
// Change the current currentNode right branch to the last element of the stack:
currentNode.right = stack.pop();
// Change left branch to null
currentNode.left = null;
// Advance by changing current currentNode to the right currentNode.
currentNode = currentNode.right;
}
else break;
}
}
是的，该算法使用Theta(N)最坏情况的时间和最坏情况的额外空间，其中N是树中的节点数。时间复杂度是显而易见的，因为您推送和弹出每个节点一次。
空间复杂性有点棘手，但例如考虑一个树，它是一个列表，其中列表的下一个元素是左子元素，但假设它对于每个列表节点中的每一个都有一个右子节点，它本身没有任何子级。
在这个例子中，你的算法将遍历左侧节点，将右侧节点添加到堆栈中，但只有在到达原始列表的末尾时才弹出这些节点，即堆栈中将有大约N/2个元素。
最好的情况是，时间复杂度仍然是Theta(N)，因为你总是遍历所有节点，但最好的情况空间复杂度是Theta(1)，因为例如，已经是列表的树永远不会将堆栈大小增加到1以上。
这通常不会被视为就地算法，因为它使用额外的Theta(N)空间，至少在最坏的情况下是这样。正如维基百科文章中所解释的那样，就地算法应该需要o(N)额外的空间，或者，我会说，通常只有O(1)或略多于此，例如 最多O((ln N)^k)一些k。应该计算最坏情况还是平均情况是另一个问题。
o(N)是小O表示法，而不是大O表示法。这意味着每个c > 0的时间/空间渐近小于c*N。 因此，Theta(N)永远不会o(N)。
此外，Theta(N)意味着它不仅O(N)，意味着渐近小于某些c > 0的c*N，而且对于某些c，它渐近大于c*N。
如果需要更严格的就地算法，则不应要求任何其他动态大小的容器。