我从一个答案中得知预订是DFS的一种:link
但是，对于平衡的二叉树，遍历树的时间复杂度为 O(logn) link，而DFS的时间复杂度为 O(N) link。
那么，预订遍历不是DFS的一种，还是我误解了这个概念？
谢谢。
最佳答案
二叉搜索树的遍历，有序或后遍历的时间复杂度始终为Θ(n)，其中为树中节点的数量。观察这种情况的一种方法是，在每种情况下，每个节点都被访问一次且恰好一次，并且每个边缘都被恰好访问了两次(一次下降，一次上升)。
您在问题中提到过，在平衡树上遍历树的时间复杂度为O(log n)。这里的O(log n)实际上是指空间复杂度(需要多少辅助内存)，而不是时间复杂度(将执行多少操作)。这样做的原因是，所有这些树遍历在其典型实现中都需要存储到目前为止已访问的节点的堆栈，以便在必要时遍历可以在树中更高级别地备份。这意味着所需的辅助空间与树的高度成比例，在平衡树中，辅助空间为O(log n)，而在任意BST中，辅助空间为O(n)。
因此，从这个意义上讲，对您问题的最佳答案可能是“BST的DFS，有序遍历，前序遍历和后序遍历总是花费相同的时间(Θ(n))，并且空间复杂度取决于高度树的 Angular ，范围在Θ(log n)和Θ(n)之间。”
关于c++ - 平衡二叉树上的预购和DFS的时间复杂度是否相同？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44766031/