題目
給定一個(gè)二叉樹秆乳，返回其節(jié)點(diǎn)值的鋸齒形層次遍歷。（即先從左往右钻哩，再從右往左進(jìn)行下一層遍歷屹堰，以此類推，層與層之間交替進(jìn)行）街氢。
例如：
給定二叉樹 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回鋸齒形層次遍歷如下：
[
[3],
[20,9],
[15,7]
]
題解
使用隊(duì)列先進(jìn)先出的特性扯键，按層將節(jié)點(diǎn)入隊(duì)，并出隊(duì)阳仔。再將出隊(duì)按層對(duì)應(yīng)順序添加到LinkedList中忧陪。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> dq = new LinkedList<>();
dq.offer(root);
boolean right = true;
while (!dq.isEmpty()) {
LinkedList<Integer> inRes = new LinkedList<>();
int levelCount = dq.size();
while (levelCount-- > 0) {
TreeNode td = dq.poll();
if (td.left != null) {
dq.offer(td.left);
}
if (td.right != null) {
dq.offer(td.right);
}
if (right) {
inRes.offerLast(td.val);
} else {
inRes.offerFirst(td.val);
}
}
right = !right;
res.add(inRes);
}
return res;
}
}
