问题描述

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回:[3,9,20,15,7]

问题分析

这个是一个比较典型的二叉树广度优先搜索:BSF,主要是利用队列的方式来作为辅助的数据结构;

  1. 获取队列大小,当前队列的大小表示该层节点个数;
  2. 调用queue的poll方法逐个打印,并把改节点的左右孩子添加到队列中;
  3. 获取最终的数组数据;

代码实现

  1. class Solution {
  2. public int[] levelOrder(TreeNode root) {
  3. if(root == null){
  4. return new int[0];
  5. }
  6. Queue<TreeNode> que = new LinkedList<>();
  7. List<Integer> list = new ArrayList<>();
  8. que.add(root);
  9. while(!que.isEmpty()){
  10. //当前层级节点的个数
  11. int size = que.size();
  12. for(int i=0; i < size; i++){
  13. TreeNode node = que.poll();
  14. list.add(node.val);
  15. if(node.left != null){
  16. que.add(node.left);
  17. }
  18. if(node.right != null){
  19. que.add(node.right);
  20. }
  21. }
  22. }
  23. int[] result = new int[list.size()];
  24. for(int j=0; j<list.size(); j++){
  25. result[j] = list.get(j);
  26. }
  27. return result;
  28. }
  29. }