題意
給定一個(gè)二叉樹(shù)掂骏，返回其節(jié)點(diǎn)值的鋸齒形層序遍歷轰驳。（即先從左往右，再?gòu)挠彝筮M(jìn)行下一層遍歷弟灼，以此類(lèi)推级解，層與層之間交替進(jìn)行）。
例如：
給定二叉樹(shù) [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回鋸齒形層序遍歷如下：
[
[3],
[20,9],
[15,7]
]
題解
利用隊(duì)列進(jìn)行求解田绑。1）每一行記錄隊(duì)列的size勤哗，然后出隊(duì)列，并把當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)塞入隊(duì)列 2）利用linkedList隊(duì)列按照方向保存節(jié)點(diǎn)數(shù)據(jù)掩驱。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ress = new ArrayList<>();
if (root == null) {
return ress;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 記錄當(dāng)前獲取到的節(jié)點(diǎn)
TreeNode curNode = root;
// 記錄方向
boolean right = true;
while (!queue.isEmpty()) {
// 記錄當(dāng)前行數(shù)據(jù)size
int size = queue.size();
LinkedList<Integer> res = new LinkedList<>();
// 每行數(shù)據(jù)出隊(duì)列芒划，直到隊(duì)列全部出完
while (size-- > 0) {
curNode = queue.poll();
// 將出隊(duì)列的節(jié)點(diǎn)左右子節(jié)點(diǎn)入隊(duì)列
if (curNode.left != null) {
queue.offer(curNode.left);
}
if (curNode.right != null) {
queue.offer(curNode.right);
}
// 根據(jù)方向，將取出來(lái)的值塞入每行的list
if (right) {
res.offerLast(curNode.val);
} else {
res.offerFirst(curNode.val);
}
}
right = !right;
ress.add(res);
}
return ress;
}
}
