平衡二叉树上的预序和 DFS 的时间复杂度是否相同？
Are time complexity of pre-order and DFS on a balanced binary tree same?
我看了一个回答说预购是DFS的一种：link
然而，对于平衡二叉树，树遍历的时间复杂度是O(logn)link and the DFS has a time complexity of O(N)link.
那么，前序遍历不是DFS的一种还是我误解了这个概念？
谢谢。
二叉搜索树的前序、中序或后序遍历的时间复杂度始终为 Θ(n)，其中 为树中的节点数。一种看待这一点的方法是，在每种情况下，每个节点都被访问一次且恰好一次，每条边恰好被访问两次（一次向下下降，一次向上上升）。
你在问题中提到，在平衡树上遍历树的时间复杂度是O(log n)。这里的O(log n)其实指的是space复杂度（需要多少辅助内存）而不是时间复杂度（要执行多少操作）。这样做的原因是，所有这些树遍历，在它们的典型实现中，都需要存储到目前为止已访问过的节点的堆栈，以便在必要时遍历可以备份到树中更高的位置。这意味着所需的辅助 space 与树的高度成正比，在平衡树中为 O(log n)，在任意 BST 中为 O(n)。
所以从这个意义上说，您问题的最佳答案可能是 "DFS, inorder traversals, preorder traversals, and postorder traversals of a BST always take the same amount of time (Θ(n)), and the space complexity depends on the height of the tree, which can range between Θ(log n) and Θ(n)."
我看了一个回答说预购是DFS的一种：link
然而，对于平衡二叉树，树遍历的时间复杂度是O(logn)link and the DFS has a time complexity of O(N)link.
那么，前序遍历不是DFS的一种还是我误解了这个概念？
谢谢。
二叉搜索树的前序、中序或后序遍历的时间复杂度始终为 Θ(n)，其中 为树中的节点数。一种看待这一点的方法是，在每种情况下，每个节点都被访问一次且恰好一次，每条边恰好被访问两次（一次向下下降，一次向上上升）。
你在问题中提到，在平衡树上遍历树的时间复杂度是O(log n)。这里的O(log n)其实指的是space复杂度（需要多少辅助内存）而不是时间复杂度（要执行多少操作）。这样做的原因是，所有这些树遍历，在它们的典型实现中，都需要存储到目前为止已访问过的节点的堆栈，以便在必要时遍历可以备份到树中更高的位置。这意味着所需的辅助 space 与树的高度成正比，在平衡树中为 O(log n)，在任意 BST 中为 O(n)。
所以从这个意义上说，您问题的最佳答案可能是 "DFS, inorder traversals, preorder traversals, and postorder traversals of a BST always take the same amount of time (Θ(n)), and the space complexity depends on the height of the tree, which can range between Θ(log n) and Θ(n)."