# 11040: 【原1040】二叉树层次遍历

### 题目描述

author: 张彦 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1040

## Description

[二叉树的遍历问题是一种精神，务必领会]

## Sample Input

``````6
0
1
1
0
4
``````

## Sample Output

``````0 1 4 2 3 5
``````

## FineArtz's solution

``````/* 二叉树层次遍历 */
#include <iostream>
using namespace std;

class Node{
public:
int l = -1, r = -1;
};

Node a[1000005];
int q[1000005] = {0};

void traverse(int root){
int front = 0, rear = 0;
q[rear++] = root;
while (front != rear){
int now = q[front++];
cout << now << ' ';
if (a[now].l != -1)
q[rear++] = a[now].l;
if (a[now].r != -1)
q[rear++] = a[now].r;
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; ++i){
int f;
cin >> f;
if (a[f].l == -1)
a[f].l = i;
else
a[f].r = i;
}
traverse(0);
return 0;
}
``````

## ligongzzz's solution

``````#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using pii = pair<int, int>;

vector<pii> tdata;

void bfs() {
queue<int> qdata;
qdata.push(0);

while (!qdata.empty()) {
auto tmp = qdata.front();
qdata.pop();

cout << tmp << " ";
if (tdata[tmp].first) {
qdata.push(tdata[tmp].first);
}
if (tdata[tmp].second) {
qdata.push(tdata[tmp].second);
}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

tdata.resize(n + 1, pii(0, 0));
for (int i = 1; i <= n - 1; ++i) {
int tmp;
cin >> tmp;
if (!tdata[tmp].first) {
tdata[tmp].first = i;
}
else {
tdata[tmp].second = i;
}
}

bfs();

return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <queue>

using namespace std;
struct treedata{
int l, r, pre;
} tree[1000001];
int n, i, node, now;
queue<int> que;

int main(){
cin>>n;
for (int i = 1; i < n; i++){
cin>>node;
tree[i].pre = node;
if (tree[node].l == 0) tree[node].l = i;
else tree[node].r = i;
}
cout<<0;
if (tree[0].l) que.push(tree[0].l);
if (tree[0].r) que.push(tree[0].r);
while (!que.empty()){
now = que.front();
que.pop();
cout<<" "<<now;
if (tree[now].l) que.push(tree[now].l);
if (tree[now].r) que.push(tree[now].r);
}
return 0;
}
``````