Solution 1：
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> sol = new ArrayList<>();
travel(root, sol, 0);
return sol;
}
private void travel(TreeNode curr, List<List<Integer>> sol, int level) {
if (curr == null)
return;
if (sol.size() <= level) {
sol.add(new ArrayList<>());
}
if (level % 2 == 0)
sol.get(level).add(curr.val);
else
sol.get(level).add(0, curr.val); //在0位置直接add，所以原来的元素右移
travel(curr.left, sol, level + 1);
travel(curr.right, sol, level + 1);
}
}
Solution 2：
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
boolean order = true;
while(!q.isEmpty()) {
int size = q.size();
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < size; ++i) {
TreeNode n = q.poll();
if(order) {
tmp.add(n.val);
} else {
tmp.add(0, n.val);
}
if(n.left != null) q.add(n.left);
if(n.right != null) q.add(n.right);
}
res.add(tmp);
order = order ? false : true;
}
return res;
}
}