# 二叉树的按层遍历

3. 自定义队列

## 示例二叉树

``````1->2->3->4->5->6->7->8->9->10->11->12->13
``````

## 数据结构

``````public static class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode() {
}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
``````

## 测评链接

LeetCode 102. Binary Tree Level Order Traversal

## 流程

``````   public static List<List<Integer>> levelOrder(TreeNode head) {
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
// 记录某个节点在第几层
Map<TreeNode, Integer> map = new HashMap<>();
// 当前是第几层
int curLevel = 0;
queue.offer(cur);
map.put(cur, curLevel);
List<Integer> levelRecords = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode c = queue.poll();
int level = map.get(c);
if (c.left != null) {
queue.offer(c.left);
map.put(c.left, level + 1);
}
if (c.right != null) {
queue.offer(c.right);
map.put(c.right, level + 1);
}
if (curLevel == level) {
} else {
levelRecords = new ArrayList<>();
curLevel = level;
}
}
// 记得要存最后一层的数据
return ans;
}
``````

``````// 遍历到的当前层的最后一个位置
TreeNode curEnd;
// 下一层的最后一个位置
TreeNode nextEnd;
``````

``````public static List<List<Integer>> levelOrder2(TreeNode head) {
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
List<Integer> levelRecords = new ArrayList<>();
TreeNode nextEnd = null;
queue.offer(curEnd);
while (!queue.isEmpty()) {
TreeNode c = queue.poll();
if (c.left != null) {
queue.offer(c.left);
// 弹出的时候，设置nextEnd
nextEnd = c.left;
}
if (c.right != null) {
queue.offer(c.right);
// 弹出的时候，设置nextEnd
nextEnd = c.right;
}
if (c == curEnd) {
// 即将要来到新的一层了
curEnd = nextEnd;
levelRecords = new ArrayList<>();
}
}
return ans;
}
``````

``````  // 自定义链表
public static class MyNode {
public TreeNode data;
public MyNode next;

public MyNode(TreeNode node) {
data = node;
}
}
// 自定义队列
public static class MyQueue {
public MyNode front;
public MyNode end;
public int size;

public MyQueue() {
front = null;
end = null;
}

public void offer(MyNode c) {
size++;
if (front == null) {
front = c;
} else {
end.next = c;
}
end = c;
}

public boolean isEmpty() {
return size == 0;
}

public MyNode poll() {
size--;
MyNode ans = front;
front = front.next;
ans.next = null;
return ans;
}

}
``````

``````    public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
MyQueue queue = new MyQueue();
MyNode nextEnd = null;
List<Integer> item = new ArrayList<>();
MyNode t;
while (!queue.isEmpty()) {
MyNode c = queue.poll();
if (c.data.left != null) {
t = new MyNode(c.data.left);
queue.offer(t);
nextEnd = t;
}
if (c.data.right != null) {
t = new MyNode(c.data.right);
queue.offer(t);
nextEnd = t;
}
if (curEnd.data == c.data) {
item = new ArrayList<>();
curEnd = nextEnd;
}
}
return ans;
}
``````

## 参考资料

原文作者：Grey Zeng
原文地址: https://www.cnblogs.com/greyzeng/p/16356829.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。