BiruLyu
5/30/2017 - 10:36 PM

## 103. Binary Tree Zigzag Level Order Traversal(BFS).java

``````/**
* 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<List<Integer>>();
if (root == null) return res;
dfs(root, 1, res);
return res;
}

private void dfs(TreeNode root, int level, List<List<Integer>> res) {
if (root == null) return;
if(res.size() < level) {
}
if(level % 2 == 0) {
res.get(level - 1).add(0, root.val);
} else {
}

dfs(root.left, level + 1, res);
dfs(root.right, level + 1, res);

}
}``````
``````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<>();
boolean order = true;
int size = 1;

while(!q.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < size; ++i) {
TreeNode n = q.poll();
if(order) {