级别顺序遍历的时间复杂度

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);
      }

}

Answer 1

这是O(n),或者确切地说Theta(n).

看一下树中的每个节点 - 每个节点最多被"访问"3次,并且至少一次) - 当它被发现时(所有节点),当从左儿子(非叶子)回来时以及何时来从右儿子(非叶子)回来,所以总共最多3*n次访问,并且至少每个节点n次访问.每次访问都是O(1)(队列推/弹),总计在 - Theta(n).