从上往下打印二叉树

题目描述：

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

分析：

二叉树的遍历：
前序遍历：根->左->右
中序遍历：左->根->右
后序遍历：左->右->根
层次遍历：一层一层，从左向右遍历。

在层次遍历中，元素需要储存有先进先出的特性，所以选用队列存储。

【思路：】
用队列来存储上一层的节点，用作遍历下一层的跟节点集合。

1. 将根结点加入队列。
2. 循环出队，并打印当前元素，若该结点有左子树，则将其加入队列，若有右子树，将其加入队列。
3. 直到队列为空，表明已经打印完所有结点。

代码：

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root == null)return list;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode tmp = q.remove();
            list.add(tmp.val);
            if(tmp.left!=null) q.add(tmp.left);
            if(tmp.right!=null) q.add(tmp.right);
        }
        return list;
    }
}

运行结果

注意：当根节点为空的时候，应该返回的是新new出来的ArrayList，而不是返回null，否则会报错。

小结：

关于队列Queue的基本方法：

add() 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常

remove() 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常

element() 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常

offer() 添加一个元素并返回true 如果队列已满，则返回false

poll() 移除并返问队列头部的元素 如果队列为空，则返回null

peek() 返回队列头部的元素 如果队列为空，则返回null

put() 添加一个元素 如果队列满，则阻塞

take() 移除并返回队列头部的元素 如果队列为空，则阻塞