BFS和DFS在二叉树上的运行时间是O(N)吗？

Question

我了解BFS和DFS在一般图上的运行时间复杂度为O(n+m)，其中n是节点数量，m是边数量，这是因为对于每个节点都必须考虑其邻接列表。然而，当BFS和DFS在二叉树上执行时，它们的运行时间复杂度是多少呢？我认为它应该是O(n)，因为一个节点可能的边数是常数（即2）。请确认这是否是正确的理解。如果不是，请说明BFS和DFS在二叉树上的正确时间复杂度。

- gmemon

---

可能是什么是广度优先和深度优先树遍历的时间和空间复杂度的重复问题。 - amit

Answer 1

BFS 和 DFS 的时间复杂度仅为O(|E|)，也就是说，在您这种情况下，时间复杂度为O(m)。

在二叉树中，m等于n-1，因此时间复杂度等同于O(|V|)。其中的m指的是总边数，而不是每个顶点的平均相邻边数。

- kevmo314

Answer 2

是的，O(n)是正确的。

同时需要注意的是，边的数量可以更精确地表示为节点数减1。这很容易理解，因为每个节点（除了根节点）都有一条从其父节点指向自身的边，而这些边包含了树中存在的所有边。

- Bernhard Barker