队列--二叉树层序遍历
/*1/ \2 3/\ /\4 5 6 7利用LinkedListQueue1. 头 [1] 尾12.头 [2 3] 尾1 23.头 [3 4 5] 尾1 24.头 [4 5 6 7] 尾1 2 35.头 [] 尾1 2 3 4 5 6 7*/代码：
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if(root == null) {return result;}LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();queue.offer(root);int c1 = 1; // 本层节点个数while (!queue.isEmpty()) {int c2 = 0; // 下层节点个数List<Integer> level = new ArrayList<>();for (int i = 0; i < c1; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.offer(node.left);c2++;}if (node.right != null) {queue.offer(node.right);c2++;}}c1 = c2;result.add(level);}return result;}// 自定义队列static class LinkedListQueue<E> {private static class Node<E> {E value;Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}}private final Node<E> head = new Node<>(null, null);private Node<E> tail = head;int size = 0;private int capacity = Integer.MAX_VALUE;{tail.next = head;}public LinkedListQueue() {}public LinkedListQueue(int capacity) {this.capacity = capacity;}public boolean offer(E value) {if (isFull()) {return false;}Node<E> added = new Node<>(value, head);tail.next = added;tail = added;size++;return true;}public E poll() {if (isEmpty()) {return null;}Node<E> first = head.next;head.next = first.next;if (first == tail) {tail = head;}size--;return first.value;}public E peek() {if (isEmpty()) {return null;}return head.next.value;}public boolean isEmpty() {return head == tail;}public boolean isFull() {return size == capacity;}}
}