如何从顶部开始逐层打印二叉树结点数据
猿媛之家
已推送大量原创内容
已出版：
C、java、python、go、php、js、kotlin、scala、c#
等各种语言的面试笔试知识点书籍
已在菜单栏开源持续更新分类整理，干货满满
三步加星，方便阅读
本题来源：微软面试题
难度指数：3 考察频率：4
题目描述：
给定一棵二叉树，要求逐层打印二叉树结点的数据，例如有如下二叉树：
对这棵二叉树层序遍历的结果为1，2，3，4，5，6，7。
分析与解答：
为了实现对二叉树的层序遍历，就要求在遍历一个结点的同时记录下它的孩子结点的信息，然后按照这个记录的顺序来访问结点的数据，在实现的时候可以采用队列来存储当前遍历到的结点的孩子结点，从而实现二叉树的层序遍历。遍历过程如下图所示。
在上图中，图（1）首先把根结点1放到队列里面，然后开始遍历。图（2）队列首元素（结点1）出队列，同时它的孩子结点2和结点3进队列；图（3）接着出队列的结点为2，同时把它的孩子结点4和结点5放到队列里。依此类推，就可以实现对二叉树的层序遍历。
实现代码如下：
import java.util.LinkedList;import java.util.Queue;public class Test{/*** 方法功能：用层序遍历的方式打印出二叉树结点的内容** 输入参数：root:二叉树根结点*/public static void printTreeLayer(BiTNode root){if(root==null) return;BiTNode p;Queue<BiTNode>queue= new LinkedList<BiTNode>();//树根结点进队列queue.offer(root);while(queue.size()>0){p=queue.poll();//访问当前结点System.out.print(p.data+" ");//如果这个结点的左孩子不为空则入队列if(p.lchild!=null)queue.offer(p.lchild);//如果这个结点的右孩子不为空则入队列if(p.rchild!=null)queue.offer(p.rchild);}}public static void main(String[] args){int arr[] = {1,2,3,4,5,6,7,8,9,10};BiTNode root;root=arraytotree(arr, 0,arr.length-1); //3.2节System.out.print("树的层序遍历结果为:");printTreeLayer (root);}}
测试数据采用了3.2节所构造的数，程序的运行结果为
树的层序遍历结果为:6 3 9 2 5 8 10 1 4 7算法性能分析：
在二叉树的层序遍历过程中，对树中的各个结点只进行了一次访问。因此，时间复杂度为O(N)。此外，这种方法还使用了队列来保存遍历的中间结点，所使用队列的大小取决于二叉树中每一层中结点个数的最大值。具有N个结点的完全二叉树的深度为h=log2N+1。而深度为h的这一层最多的结点个数为2h-1=n/2。也就是说，队列中可能的最多的结点个数为N/2。因此，这种算法的空间复杂度为O(N)。
引申：用空间复杂度为O(1)的算法来实现层序遍历。
上面介绍的算法的空间复杂度为O(N)，显然不满足要求。通常情况下，提高空间复杂度都是要以牺牲时间复杂度作为代价的。对于本题而言，主要的算法思路：不使用队列来存储每一层遍历到的结点，而是每次都会从根结点开始遍历。把遍历二叉树的第k层的结点，转换为遍历二叉树根结点的左右子树的第k-1层结点。实现代码如下：
int printAtLevel(BiTNode root, intlevel){if(root==null || level< 0)return 0;elseif(level == 0){System.out.println(root.data);return 1;}else/*** 把打印根结点level层的结点转换为求解根结点的孩子结点的level-1** 层的结点。*/return printAtLevel(root.lchild, level - 1) +printAtLevel(root.rchild, level - 1);}
通过上述算法，可以首先求解出二叉树的高度h，然后调用上面的函数h次就可以打印出每一层的结点。
感谢您的阅读，有任何问题欢迎评论区留言。