百度口试（树层次遍历）

百度面试（树层次遍历）
换行问题其实在于如何表达一层的结束。书上采用了游标，而第一个尝试则用了两个队列。本人想到第三个可行方案，是把一个结束信号放进队列里。由于使用queue<Node*>，可以插入一个空指针去表示一层的遍历结束。

void PrintNodeByLevel(Node* root) {
queue<Node*> Q;
Q.push(root);
Q.push(0);
do {
Node* node = Q.front();
Q.pop();
if (node) {
cout << node->data << " ";
if (node->pLeft)
Q.push(node->pLeft);
if (node->pRight)
Q.push(node->pRight);
}
else if (!Q.empty()) {
Q.push(0);
cout << endl;
}
} while (!Q.empty());
}
这个实现的代码很贴近之前的PrintBFS()，也只有一个循环。注意一点，当发现空指针(结束信号)时，要检查队列内是否还有节点，如果没有的话还插入新的结束信号，则会做成死循环。