给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
解题思路：使用层次遍历，将LinkedList当做双向链表使用。
class Solution { //LinkeList双向链表,add插入到尾部,,push插入到头部 public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null ) return res; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); int level = 0; while(!queue.isEmpty()){ int size = queue.size(); LinkedList<Integer> temp = new LinkedList<Integer>(); for(int i = 0; i < size; i++){ root = queue.poll(); if((level&1) == 1) //如果是奇数层,就push插入到双向链表的头部 temp.push(root.val); else{ //如果是偶数层,就add插入到双向链表尾部 temp.add(root.val); } if(root.left != null){ queue.add(root.left); } if(root.right != null){ queue.add(root.right); } } // if((level&1) == 1){ // Collections.reverse(temp); // } res.add(temp); level++; } return res; }}