剑指32-1

剑指 Offer32-I.从上到下打印二叉树

---

题目要求：

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印.

例如：给定二叉树[3,9,20,null,null,15,7]

    3
   / \
  9  20
     / \
    15 7 

返回：[3,9,20,15,7]

题目分析:

• 对二叉树进行打印实际就是对其进行遍历，根据题目要求，同一层节点按照从左到右的顺序进行遍历，所以应采用层序遍历的方法去遍历。
• 层序遍历：借助队列进行实现，要保证读取当前节点后，接下里读取器左右节点，然后是左子节点的左右节点，然后是右子节点的左右节点。起初思路有些错误，想通过递归去进行读取，但是递归一旦深入到一棵子树中，便会继续深入下去，是无法返回保证按层读取的，实际上并不需要递归处理。
• 通过队列实现层序遍历：首先将根节点加入队列，然后当队列不为空时进入循环，每一次循环，取出队列头结点，并读取节点数据，然后将其左右节点加入队列（子节点不为空），这样的话，下一次左子节点从队列头取出，同时将其左右子节点加入队列，这样就保证了队列中的数据顺序是按照层序遍历的顺序弹出的。
• 注意事项：针对根节点为空，做出针对处理。队列集合对象为Integer,先用Integer数组保存数据，然后转化成int[],返回数组。

代码实现：

class Solution {

ArrayList<Integer> b = new ArrayList<Integer>(1004);
Queue<TreeNode> q = new ArrayDeque<>(1004);
public int[] levelOrder(TreeNode root) {
    if(root == null) {
        int[] a = new int[0];
        return a;
    }
    q.add(root);
    int i = 0;
    TreeNode tem  =  new TreeNode(0) ;
    while(!(q.isEmpty())){
        tem = q.remove();
        b.add(tem.val);
        if(tem.left != null){
            q.add(tem.left);
        }
        if(tem.right != null){
            q.add(tem.right);
        }
    }
    int[] a = new int[b.size()];
    Iterator<Integer> in = b.iterator();
    while(in.hasNext()){
        a[i++] = in.next();
    }
    return a;
    }
}

通过本题主要复习一下使用队列进行层序遍历，以及熟悉Markdown写法。