队列--二叉树层序遍历

/*
              1
             / \
            2   3
           /\   /\
          4  5 6  7
         利用LinkedListQueue
         1. 头 [1] 尾
            1
         2.头 [2 3] 尾
            1 2
         3.头 [3 4 5] 尾
            1 2
         4.头 [4 5 6 7] 尾
            1 2 3
         5.头 [] 尾
            1 2 3 4 5 6 7
 */

代码：

class Solution {
    public List> levelOrder(TreeNode root) {
        List> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        LinkedListQueue queue = new LinkedListQueue<>();
        queue.offer(root);
        int c1 = 1;		// 本层节点个数
        while (!queue.isEmpty()) {
            int c2 = 0; 	// 下层节点个数
            List 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 {
 
        private static class Node {
            E value;
            Node next;
 
            public Node(E value, Node next) {
                this.value = value;
                this.next = next;
            }
        }
 
        private final Node head = new Node<>(null, null);
        private Node 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 added = new Node<>(value, head);
            tail.next = added;
            tail = added;
            size++;
            return true;
        }
 
        public E poll() {
            if (isEmpty()) {
                return null;
            }
            Node 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;
        }
    }
}