层序遍历的时间复杂度

Question

二叉树层序遍历的时间复杂度是什么？是O(n)还是O(log n)？

void levelorder(Node *n)
{    queue < Node * >q;
     q.enqueue(n);

     while(!q.empty())
      {
         Node * node = q.front();
         DoSmthwith node;
         q.dequeue();          
         if(node->left != NULL)
         q.enqueue(node->left);
         if (node->right != NULL)
         q.enqueue(node->right);
      }

}

- Fatima

Answer 1

这是一个 O(n) 的算法，确切地说是 Theta(n)。

我们来看看树中的每个节点 - 每个节点最多被 "访问" 3 次，并且至少一次。当它被发现时（所有节点），从左侧子节点返回（非叶子）和从右侧子节点返回（非叶子）时各访问一次。因此，每个节点最多访问 3n 次，至少访问 n 次。每次访问的时间为 O(1)（队列推入/弹出），总共为 Theta(n)。

- amit

Answer 2

解决这个问题的另一种方法是识别出层序遍历与图的广度优先搜索非常相似。广度优先遍历的时间复杂度为O(|V| + |E|)，其中|V|是顶点数，|E|是边数。

在树中，边的数量大约等于顶点的数量。这使得它总体上是节点数量的线性。

特别地，由于树中每个节点（除了根节点）都有一个入边（来自其一个父节点），我们得到|E| = |V| - 1。

因此，O(|V| + |E|) = O(|V| + |V| - 1) = O(|V|)。

- Anirudh Ramanathan

Answer 3

时间和空间复杂度均为O(n)。其中n为节点数。

空间复杂度 - 队列大小与节点数成正比，即O(n)

时间复杂度 - 每个节点被访问两次，一次在入队操作中，一次在出队操作中，因此为O(n)

这是BFS的特殊情况。您可以阅读有关BFS（广度优先搜索）的内容http://en.wikipedia.org/wiki/Breadth-first_search。

- Manish Mulani