Article Outline
TOC
Collection Outline
1.题目
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
2.思路
通过上面的具体例子分析,可以找到规律:每一次打印一个节点的时候,如果该节点有子节点,则把该节点的子节点放到一个队列的尾部。接下来到对队列的头部取出最早进入队列的节点放到ArrayList 中,重复前面的操作,直至队列中所有的节点都存到ArrayList中。
3.题解
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) {
ArrayList<Integer> resultList = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(root == null){
return resultList;
}
deque.add(root);
while(!deque.isEmpty()){
TreeNode node = deque.getFirst();
deque.pollFirst();
resultList.add(node.val);
if(node.left != null){
deque.add(node.left);
}
if(node.right != null){
deque.add(node.right);
}
}
return resultList;
}
}
4.补充
4.1理解Java集合之---Deque
4.2接口
interface Deque <E>
线性集合,支持两端的元素插入和移除。Deque是double ended queue
的简称,习惯上称之为双端队列。大多数Deque 实现对它们可能包含的元素的数量没有固定的限制,但是该接口支持容量限制的deques以及没有固定大小限制的deque。
4.3Deque与Queue区别
Deque同时扩展了Queue接口,当Deque作为队列的时候,会产生FIFO(先进先出)行为。元素添加在双端队列的末尾并从头开始删除。
4.4 Stack和Deque方法的比较
4.5 Deque的使用场景
在一般情况,不涉及到并发的情况下,有两个实现类,可根据其自身的特性进行选择,分别是:
- LinkedList 大小可变的链表双端队列,允许元素为插入null。
- ArrayDeque 大下可变的数组双端队列,不允许插入null。
- ConcurrentLinkedDeque 大小可变且线程安全的链表双端队列,非阻塞,不允许插入null。
- LinkedBlockingDeque 为线程安全的双端队列,在队列为空的情况下,获取操作将会阻塞,直到有元素添加。
- LinkedList 和 ArrayDeque 是线程不安全的容器。