题目描述

二叉树的层序遍历 对给定的二叉树进行层序遍历，按照从上到下、从左到右的顺序，依次输出二叉树中各个节点的编号。

输入格式

第一行是一个整数 n，表示二叉树的节点个数。 接下来的 n 行，每行对应一个节点（按节点编号 1 到 n 的顺序输入）。每行包含两个整数，分别表示该节点的左孩子编号和右孩子编号。如果孩子不存在，则用 -1 表示。

输出格式

一行数据，包含按层序遍历顺序访问到的节点编号，编号之间用空格分隔。

样例

输入样例 1

3
2 3
-1 -1
-1 -1

输出样例 1

1 2 3

输入样例 2

7
2 3
4 5
6 7
-1 -1
-1 -1
-1 -1
-1 -1

输出样例 2

1 2 3 4 5 6 7

输入样例 3

6
2 3
4 5
6 -1
-1 -1
-1 -1
-1 -1

输出样例 3

1 2 3 4 5 6

输入样例 4

4
-1 2
-1 3
-1 4
-1 -1

输出样例 4

1 2 3 4