题意：
层次遍历二叉树，S型遍历
分析：
其实就是层次遍历，考虑用队列实现，如何反序呢？考虑用栈实现。至于层次，打个变量标记下就是了。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> list = new ArrayList<>(); Queue<TreeNode> q = new LinkedList<>(); int layer = 0; if(root==null) return list; q.add(root); while(!q.isEmpty()){ Stack<Integer> s = new Stack<>(); List<Integer> l = new ArrayList<>(); int size = q.size(); layer++; for(int i=0; i<size; i++){ TreeNode node = q.poll(); if(layer%2==0){ s.push(node.val); }else{ l.add(node.val); } if(node.left!=null) q.offer(node.left); if(node.right!=null) q.offer(node.right); } if(layer%2==0){ while(!s.isEmpty()){ l.add(s.pop()); } } list.add(new ArrayList(l)); } return list; } }