层序遍历的时间复杂度

二叉树层次顺序遍历的时间复杂度是多少？是 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);
      }

}

It is O(n)，或者准确地说Theta(n).

查看树中的每个节点 - 每个节点最多被“访问”3 次，至少一次） - 当它被发现时（所有节点），当从左儿子（非叶子）返回时以及当来时从右子（非叶子）返回，因此总共最多 3*n 次访问，每个节点至少 n 次访问。每次访问都是O(1)（队列推送/弹出），总计 -Theta(n).