Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
一刷
题解：用DFS，在子函数内传入level信息，并通过level的奇偶判断加在list首部还是尾部（所以list为linkedlist)
/**
* 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>> res = new ArrayList<>();
travel(root, res, 0);
return res;
}
private void travel(TreeNode curr, List<List<Integer>> sol, int level){
if(curr == null) return;
if(sol.size()<=level){
List<Integer> newLevel = new LinkedList<>();
sol.add(newLevel);
}
List<Integer> collection = sol.get(level);
if(level%2 == 0) collection.add(curr.val);//left to right
else collection.add(0, curr.val);//rigth to left
travel(curr.left, sol, level+1);
travel(curr.right, sol, level+1);
}
}
