每天一道算法题——

前言：
昨天写好的忘记发了。今天的也要补上。

题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
测试用例:
{10,6,14,4,8,12,16}
对应输出应该为:
[10,6,14,4,8,12,16]

分析：

使用两个队列一个存放节点，一个存放值。先将根节点加入到队列中，然后遍历队列中的元素，遍历过程中，访问该元素的左右节点，再将左右子节点加入到队列中来

源码：

import java.util.ArrayList;
import java.util.Stack;

public class Test1 {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> arrayList = new ArrayList<Integer>();//存放值
    ArrayList<TreeNode> queue = new ArrayList<TreeNode>();//存放节点
    if (root!=null) {//如果传入的树不为空
        queue.add(root);//将树的根节点root放入节点记录到队列queue中
        while(queue.size()!=0){
            TreeNode node = queue.remove(0);//从上往下打印，先将头结点赋给node
            //从左往右遍历
            if (node.left!=null) {//若头结点存在左子树
                queue.add(node.left);//将左子树记录在queue中
            }
            if (node.right!=null) {//若头结点存在右子树
                queue.add(node.right);//将右子树记录在queue中
            }
            arrayList.add(node.val);//在值队列中记录该节点的值

        }
    }
        return arrayList;
    }
}



class TreeNode {//树的类定义
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}

运行测试：

运行时间：18ms
占用内存：8720k

总结：
此题重点考验了对数据结构的理解。数的层次遍历一般都是借助队列来实现。我们所需要做的仅仅只是使用ArrayList来模拟一个队列。