l2-035 完全二叉树的层序遍历 (25 分)

题目描述

给定一棵完全二叉树，要求对该二叉树进行层序遍历。

输入格式

第一行包含一个正整数 N (≤100)，表示完全二叉树的结点数。第二行给出完全二叉树的 N 个结点的编号（从1到N，按层序递增），数字间以空格分隔。如果某结点不存在，则传入的编号为 −1。

输出格式

对给定的完全二叉树进行层序遍历，输出每个结点的编号。数字间以 1 个空格分隔，行末不能有多余空格。

输入样例

10
1 2 3 4 5 6 7 8 9 10

输出样例

1 2 3 4 5 6 7 8 9 10

算法1

(队列) $O(n)$

完全二叉树的层序遍历，可以使用队列来实现。首先将根节点入队，然后每次从队列中取出一个节点，输出该节点的值，并将其左右子节点入队。直到队列为空，遍历结束。

时间复杂度

遍历完所有节点，时间复杂度为 $O(n)$。

C++ 代码

算法2

(递归) $O(n)$

完全二叉树的层序遍历，也可以使用递归来实现。对于每一层，先遍历左子树，再遍历右子树。遍历完所有层，遍历结束。

时间复杂度

遍历完所有节点，时间复杂度为 $O(n)$。

C++ 代码