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

思路：利用队列实现树的层序遍历。

Python:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        result = []
        queue = []
        #若根节点为空，返回空列表
        if root == None:
            return []
        #根结点入队
        queue.append(root)
        while queue != []:
            #队首结点出队
            node = queue.pop(0)
            #取队首结点元素
            result.append(node.val)
            #层序遍历左右子结点先后入队
            if node.left != None:
                queue.append(node.left)
            if node.right != None:
                queue.append(node.right)
        return result

Java:

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<TreeNode> queue = new LinkedList<>();//队列
        ArrayList<Integer> resultList = new ArrayList<>();//返回列表
        if(root == null){
            return resultList;//若根节点为空直接返回
        }
        queue.offer(root);//根节点入队
        //若队列不为空，则继续层序遍历
        while(queue.size() != 0){
            TreeNode node = queue.poll();//队首结点出队
            resultList.add(node.val);//存入队首结点元素值
            //层序遍历左右结点先后入队
            if(node.left != null)
                queue.offer(node.left);
            if(node.right != null)
                queue.offer(node.right);
        }
        return resultList;
    }
}