从上往下打印二叉树

题目描述

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

代码格式

import java.util.ArrayList;
/**
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) {        
    }
}

解题

1.思路
该题实质考察树的遍历算法。（树的知识点参考：点击打开链接）

image.png
第一步：先判断根节点是否为空，如果为空则返回空链表，如果不为空则执行第二步；
第二步：将该节点保存在一个队列（作为容器，队列具有先进先出的特点，先将跟节点放入容器，判断其左右子节点是否存在，如果存在，依次将左右子节点保存在队列的尾部）中；
第三步：接下来到对队列的头部取出最早进入队列的节点放到ArrayList 中，重复前面的操作，直至队列中所有的节点都存到ArrayList中。
2.代码如下：

import java.util.ArrayList;
import java.util.Deque;
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) {
        //定义Integer泛型
        ArrayList<Integer> list=new ArrayList<Integer>();
        //如果根结点为空，返回空链表
        if(root==null){
            return list;  
        }
        //定义一个双向队列
        Deque<TreeNode> deque=new LinkedList<TreeNode>();
        //将根结点插入队列
        deque.add(root);
        //进行判断
        while(!deque.isEmpty()){
            //队列的头部取出最早进入队列的节点
            TreeNode treenode=deque.pop();
            //放到ArrayList 中
            list.add(treenode.val);
            //判断作业结点
            if(treenode.left!=null){
                deque.add(treenode.left);
            }
            if(treenode.right!=null){
                deque.add(treenode.right);
            }
        }
        return list;
    }
}

补充知识点：

java的Deque与Queue

1.Queue接口（单向队列）

Queue接口，是集合框架Collection的子接口，是一种常见的数据结构，遵循先进先出的原则。
是基于链表来进行实现，的单向队列。
LinkedList接口，实现了Queue，所以LinkedList，在插入和删除操作，效率会比较高。
poll（）：将队首的元素删除，并返回该元素。
peek（）：返回队首的元素，但不进行删除操作。
offer（）：将元素添加到队尾，如果成功，则返回true。

2.Deque接口（双向队列）

Deque接口，是Queue接口的子接口，是指队列两端的元素，既能入队（offer）也能出队。
如果将Deque限制为只能从一端进行入队，和出队，就是栈的数据结构的实现。对于栈而言，有入栈（push）和出栈（pop），遵循先进后出的规则。
双端队列：
add(（e）\offer（e）：将元素增加到队列的末尾，如果成功，返回true。
remove（）\poll（）:将元素从队列的末尾删除。
element（）\peek（）：返回队首的元素，但不进行删除。
栈：
push（e）:入栈
pop（e）:出栈
peek（）:返回栈首元素，但不进行删除。原文链接