二叉树：折返遍历

二叉树：折返遍历

    给定一棵二叉树，输出对其按层折返遍历的结果，即对于一层从左往右遍历，一层从右往左遍历。如下面的二叉树，其折返遍历结果为[[3], [20, 9], [15, 7]]。

    分析：按照层级遍历的顺序访问，把每层的访问结果存入List中，存储的时候，奇数层的值插入队列末尾，偶数层的插入队列头即可得到想要的结果。

    实际上这种方法并不是真正的折返遍历，只不过对访问的结果做了处理。如果想要真正按照折返的顺序进行访问，在节点插入queue时作处理即可，不过相对麻烦一点。

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<List<Integer>>();if(root == null)return result;LinkedList<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);boolean left2right = true;while(!queue.isEmpty()){LinkedList<Integer> subList = new LinkedList<Integer>();int levelNum = queue.size();for(int i = 0; i < levelNum; i++){TreeNode node = queue.poll();if(left2right)  subList.add(node.val);elsesubList.addFirst(node.val);if(node.left != null) queue.offer(node.left);if(node.right != null)queue.offer(node.right);}left2right = !left2right;result.add(subList);}return result;}