- /*
- 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;
- }
- }
- }