image.png
解题思路
此题与上一题的差别只在于将节点添加到level这个变量的方式
我们使用一个布尔变量记录每一层是从左到右还是反过来
如果是从左到右则将节点添加到队列尾部level.addLast(head.val)
否则添加到首部level.addFirst(head.val)
代码
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
boolean leftToRight = false;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
leftToRight = !leftToRight;
// 这里的size一定要放在外面, 不能放在for语句的循环条件
int size = queue.size();
// level用于存放本层的所有节点
Deque<Integer> level = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode head;
head = queue.remove();
if (head.left != null) {
queue.add(head.left);
}
if (head.right != null) {
queue.add(head.right);
}
// 根据是否从左到右来决定添加到头还是尾
if (leftToRight) {
level.addLast(head.val);
} else {
level.addFirst(head.val);
}
}
result.add(new LinkedList<>(level));
}
return result;
}
}
