剑指OfferJZ22：从上往下打印二叉树-java版

JZ22:从上往下打印出二叉树的每个节点，同层节点从左至右打印。

深搜（dfs） 深搜，看名字就知道到是优先往深处找，不撞南墙终不悔。深搜，像是一个人走迷宫，遇见岔路不知道怎么走，就瞎选一个（程序中一搬从头遍历），走到底，不对，回到岔路口，选另一条路，接着走。

深搜的实现一般用栈或递归，不断深入。

宽搜（bfs） 宽搜全名宽度搜索，就是放宽了搜，就像是雷达那样，中间一个点不断放出电磁波，一圈一圈往外扩散，很容易就能发现目标，而且发现了必然就是最近的（最优解）。

宽搜的实现一般使用队列，不断扩散。

根据题意可知使用宽搜方法

public class jz22 {
    public ArrayList PrintFromTopToBottom(TreeNode root) {

        ArrayList ans = new ArrayList();
        Queue queue = new LinkedList();//放入遍历二叉树的节点（本质上是维护宽搜的）
        if(root!=null){
            queue.add(root);
        }
        //迭代的过程-->宽搜
        while(!queue.isEmpty()){
            TreeNode node=queue.peek();//peek()返回队列的头元素，不删除
            ans.add(node.val);//将当前节点的val值放入ArrayList中
            //同层节点从左至右打印
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
            queue.poll();//poll()返回队列的头元素，并删除；当前节点val值已经放入ans中，所以要删去
        }
        return ans;
    }
}