二叉树的广度遍历

//思路：此题实际为二叉树的广度遍历，广度遍历必须借助其他的数据结构才能进行，比如最常见的Queue
//(不能直接递归哦)
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) {
        //queue用来保存当前遍历到了哪个节点，一次性把一个节点的左右子都入队
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //list用来保存输出的节点
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(root==null){//注意：空树返回一个默认构造的空LinkedList，而不是一个空指针null
            return list;
        }
        TreeNode current = root;
        queue.offer(current);
        //只要队列中还有节点就说明还没遍历完，继续。
        //每次从队列出队，然后将这个节点左右子入队列（FIFO，故能完成广度/层级遍历），再将这个节点记录在list中即可。
        while(!queue.isEmpty()){
            current = queue.poll();
            list.add(current.val);
            if(current.left!=null){//有左子则入队
                queue.offer(current.left);
            }
            if(current.right!=null){
                queue.offer(current.right);
            }
        }
        return list;
    }
}