3.3 如何从顶部开始逐层遍历二叉树结点数据

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

给定一棵二叉树，要求逐层打印二叉树结点的数据，例如有如下二叉树：

对这棵二叉树层序遍历的结果为1，2，3，4，5，6，7。

分析与解答：

为了实现对二叉树的层序遍历，就要求在遍历一个结点的同时记录下它的孩子结点的信息，然后按照这个记录的顺序来访问结点的数据，在实现的时候可以采用队列来存储当前遍历到的结点的子结点，从而实现二叉树的层序遍历，遍历过程如下图所示。

在上图中，1）首先把根结点1放到队列里面，然后开始遍历。2）队列首元素（结点1）出队列，同时它的子结点2和3进队列；3）接着出队列的结点为2，同时把它的孩子结点4和5放到队列里，以此类推就可以实现对二叉树的层序遍历。

实现代码如下：

测试数据采用了3.2节所构造的数，程序的运行结果为

算法性能分析：

在二叉树的层序遍历过程中，对树中的各个结点只进行了一次访问，因此，时间复杂度为 O（n），此外，这个方法还使用了队列来保存遍历的中间结点，所使用队列的大小取决于二叉树中每一层中结点个数的最大值。具有N个结点的完全二叉树的深度为h=log₂ⁿ+1。而深度为h的这一层最多的结点个数为2^h-1=n/2。也就是说队列中可能的最多的结点个数为n/2。因此，这种算法的空间复杂度为O（n）。

引申：用空间复杂度为O（1）的算法来实现层序遍历。

上面介绍的算法的空间复杂度为O（n），显然不满足要求。通常情况下，提高空间复杂度都是要以牺牲时间复杂度作为代价的。对于本题而言，主要的算法思路为：不使用队列来存储每一层遍历到的结点，而是每次都会从根结点开始遍历。把遍历二叉树的第 k 层的结点，转换为遍历二叉树根结点的左右子树的第k-1层结点。算法如下所示：

通过上述算法，可以首先求解出二叉树的高度 h，然后调用上面的函数 h 次就可以打印出每一层的结点。