103. Binary Tree Zigzag Level Order Traversal
# Medium, BFS
Most are as same as #102. Set a flag to judge odd or even layer. Once it's even layer, reverse the level then append to result.
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public void DFS(TreeNode root, int level) {
if(root == null) return;
if(res.size() == level)
res.add(new ArrayList<Integer>());
if(level%2 == 1)
res.get(level).add(0, root.val);
else
res.get(level).add(root.val);
if(root.left != null) DFS(root.left, level + 1);
if(root.right != null) DFS(root.right, level + 1);
}
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
DFS(root, 0);
return res;
}
}class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
List<Integer> level = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
int even = 1;
queue.add(root);
while(!queue.isEmpty()) {
level = new ArrayList<Integer>();
int l = queue.size();
while(l > 0) {
TreeNode node = queue.poll();
level.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
l --;
}
if(even == -1)
Collections.reverse(level);
res.add(level);
even *= (-1);
}
return res;
}
}Last updated
Was this helpful?