问平衡二叉树上预序和DFS的时间复杂度是否相同？

EN

二进制搜索树的预定、排序或后置遍历的时间复杂度总是Θ(n)，其中是树中的节点数。看到这一点的一种方法是，在每种情况下，每个节点被访问一次，精确地访问一次，而每个边缘被访问两次(一次向下下降，一次向上上升)。

您在问题中已经提到，在平衡树上遍历树的时间复杂性是O(log )。这里的O(log )实际上指的是空间复杂度(需要多少辅助内存)，而不是时间复杂度(将执行多少次操作)。原因是，所有这些树遍历，在它们的典型实现中，都需要存储到目前为止访问过的节点的堆栈，以便在必要时遍历能够在树中备份到更高的位置。这意味着所需的辅助空间与树的高度成正比，在平衡树中为O(log )，在任意BST中为O(n)。

因此，从这个意义上说，对您的问题最好的答案可能是"DFS，BST的顺序遍历、前置遍历和后置遍历总是花费相同的时间(Θ( n) )，空间复杂度取决于树的高度，树的高度可以介于Θ(log N)和Θ(N)之间。“