2021/05/04
仍然是层次遍历
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) return Collections.emptyList();
LinkedList<TreeNode> q = new LinkedList<>();
TreeNode p = root;
q.offer(p);
List<List<Integer>> res = new ArrayList<>();
boolean reverse = false;
while (!q.isEmpty()) {
LinkedList<Integer> cur = new LinkedList<>();
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
p = q.poll();
if (reverse) {
cur.addFirst(p.val);
} else {
cur.add(p.val);
}
if (p.left != null) q.offer(p.left);
if (p.right != null) q.offer(p.right);
}
res.add(cur);
reverse = !reverse;
}
return res;
}
}
严格按照要求的顺序遍历
每一次都反转整个 queue，可以模拟出之字遍历的效果，但是要考虑到，如果反转之后，每次 pop 出一个结点，得先添加右结点，再添加左结点。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) return Collections.emptyList();
LinkedList<TreeNode> q = new LinkedList<>();
TreeNode p = root;
q.offer(p);
List<List<Integer>> res = new ArrayList<>();
boolean reverse = false;
while (!q.isEmpty()) {
List<Integer> cur = new ArrayList<>();
int levelSize = q.size();
Collections.reverse(q);
for (int i = 0; i < levelSize; i++) {
p = q.poll();
cur.add(p.val);
if (reverse) {
if (p.right != null) q.offer(p.right);
if (p.left != null) q.offer(p.left);
} else {
if (p.left != null) q.offer(p.left);
if (p.right != null) q.offer(p.right);
}
}
res.add(cur);
reverse = !reverse;
}
return res;
}
}