广度优先和深度优先的树遍历的时间和空间复杂度是多少？

广度优先和深度优先的树遍历的时间和空间复杂度是多少？

BFS：

时间复杂度为

O(|V|)

，其中

|V|

为节点数。您需要遍历所有节点。
空间复杂度也是

O(|V|)

如此-因为在最坏的情况下，您需要将所有顶点保持在队列中。

DFS：

时间复杂度又来了

O(|V|)

，您需要遍历所有节点。
空间复杂度-取决于实现，递归实现可能具有

O(h)

空间复杂度（最坏的情况），其中

h

树的最大深度。
在堆栈上使用迭代解决方案实际上与BFS相同，只是使用堆栈而不是队列-这样您会同时增加

O(|V|)

时间和空间复杂度。

（*）请注意，树的空间复杂度和时间复杂度与一般图略有不同，因为您不需要维护

visited

树的集合，并且

|E| =O(|V|)

，因此该

|E|

因素实际上是多余的。