剑指Offer面试题：25.从上往下打印二叉树

一、题目
————————————————
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

————————————————
二、思路
————————————————
这道题实质是在考查树的遍历算法。只是这种遍历不是我们熟悉的前序（根左右）、中序（左根右）、后序（左右根）遍历。故就需要从树及打印列表分析。分析上图二叉树的层次打印顺序

通过上图的具体例子的分析，我们可以找到从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。
————————————————
三、解决问题
————————————————
二叉树结点的定义如下：

package swordoffer;

/**
 * 二叉树结点的定义
 * @author LQ
 * @version 1.0
 * @date 2020-03-13 15:56
 */
public class TreeNode {
    int val;

    TreeNode left;

    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

代码实现：

package swordoffer;

/**
 * @author LQ
 * @version 1.0
 * @date 2020-04-26 10:43
 */

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/**
 * 题目描述
 * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 */

public class Solution25 {
    public static void main(String[] args) {
        TreeNode root = createBinaryTree();
        System.out.println(new Solution25().PrintFromTopToBottom(root));
    }
    /**
     * 思路：
     * 1、利用队列进行层次遍历
     * 2、每次弹出队列中的一个元素，并把左右孩子加入队列即可
     */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        //queue用来保存当前遍历到了哪个节点，一次性把一个节点的左右子都入队
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //list用来保存输出的节点
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(null == root){//注意：空树返回一个默认构造的空LinkedList，而不是一个空指针null
            return list;
        }
        //当前处理的节点
        TreeNode current = root;
        //将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时
        //此方法通常要优于add(E)，后者可能无法插入元素，而只是抛出一个异常。
        queue.offer(current);
        //只要队列中还有节点就说明还没遍历完，继续。
        //每次从队列出队，然后将这个节点左右子入队列（FIFO，故能完成广度/层级遍历），再将这个节点记录在list中即可。
        while(!queue.isEmpty()){
            //弹出队列中的一个元素
            current = queue.poll();
            //将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true
            //如果当前没有可用的空间，则抛出 IllegalStateException
            list.add(current.val);//相当于打印
            // 左右孩子入队列
            if(current.left != null){//有左子则入队
                queue.offer(current.left);
            }
            if(current.right != null){
                queue.offer(current.right);
            }
        }
        return list;
    }
    private static TreeNode createBinaryTree() {
        TreeNode root = new TreeNode(8);
        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(10);

        root.left = node1;
        root.right = node2;

        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(9);
        TreeNode node6 = new TreeNode(11);

        node1.left = node3;
        node1.right = node4;

        node2.left = node5;
        node2.right = node6;

        return root;
    }
}

————————————————

————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。