平衡二叉树上预序和DFS的时间复杂度相同吗?

二叉搜索树的前序、顺序或后序遍历的时间复杂度始终为Θ(n),其中是树中的节点数。一种方法是,在每种情况下,每个节点只访问一次,每个边只访问两次(一次向下下降,一次向上上升)。

空间复杂性 时间复杂性 (将执行多少操作)。原因是,所有这些树遍历在其典型实现中都需要存储迄今为止访问过的节点堆栈,以便在必要时遍历可以备份到树的更高位置。这意味着所需的辅助空间与树的高度成正比,在平衡树中,树的高度为O(log n),在任意BST中为O(n)。

因此,从这个意义上说,您的问题的最佳答案可能是“BST的DFS、有序遍历、前序遍历和后序遍历总是花费相同的时间((n)),空间复杂度取决于树的高度,其范围可以在Θ(log n)和920e(n)之间。”