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

题目

题目描述

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

Description

给出一棵二叉树，求它的层次遍历结果。

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

Input Format

第一行，N<1000000，表示二叉树节点数。

默认序号为0的节点为树根。接下来共N-1行，依次表示序号为1，...，N-1的节点的父亲节点序号。

如果一个节点有两个孩子节点，左孩子节点序号总是小于右孩子节点序号。

Output Format

仅一行，二叉树的层次遍历结果。节点序号间用空格隔开。

Hint

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