Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
3
/ \
9 20
/ \
15 7
[
[3],
[20,9],
[15,7]
]
这就是广度优先遍历的变种，使用队列，每个一层换一个顺序入队出队，哈哈js可以随便换队列方向
var zigzagLevelOrder = function(root) {
if (!root)
return [];
var q = [root];
var res = [];
var flag = true;
while (q.length!==0) {
var lastLength = q.length;
res.push([]);
if (flag) {
for (let i = 0;i < lastLength;i++) {
let temp = q.shift();
res[res.length - 1].push(temp.val);
if (temp.left)
q.push(temp.left);
if (temp.right)
q.push(temp.right);
}
} else {
for (let i = 0;i < lastLength;i++) {
let temp = q.pop();
res[res.length - 1].push(temp.val);
if (temp.right)
q.unshift(temp.right);
if (temp.left)
q.unshift(temp.left);
}
}
flag = !flag;
}
return res;
};
