题目大意：
二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回锯齿形层次遍历如下：
[ [3], [20,9], [15,7] ]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=103
解题思路分析：
之前文章多次讲过，二叉树问题多数情况下应该想到使用dfs或者bfs来解题。本题要求逐行打印，因此bfs相对来说更加适合。
利用bfs广度优先搜索遍历二叉树每一行，如果当前行是偶数行，则正序向返回结果插入数据，反之则逆序插入。bfs的部分完全是模板级别的代码，这里就不在多说了。
实现代码：
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
// 返回结果
List<List<Integer>> res = new ArrayList<>();
// root为空，返回res
if(root==null) return res;
// bfs用的Queue
Queue<TreeNode> q = new LinkedList<>();
// 将root加入Queue
q.offer(root);
// 当前行数
int level=0;
// 以下为bfs常规代码
while(q.size()>0){
int size=q.size();
// 保存当前行所有节点
List list = new ArrayList<>();
// 逐行遍历二叉树
while(size>0){
// 取出当前节点
TreeNode n = q.poll();
size--;
// 如果是偶数行，正序插入
if(level%2==0) list.add(n.val);
// 奇数行，倒序插入
else list.add(0, n.val);
// 左节点不为空，将左节点加入Queue
if(n.left!=null)q.offer(n.left);
// 右节点不为空，将右节点加入Queue
if(n.right!=null)q.offer(n.right);
}
// 行数加一
level++;
// 将当前行加入返回结果
res.add(list);
}
return res;
}本题解法执行时间为3ms。
Runtime: 3 ms, faster than 74.98% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
Memory Usage: 43.3 MB, less than 5.77% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-103-binary-tree-zigzag-level-order-traversal-解题思路分析/