# Java Iteratively(BFS) and Recursively(DFS) beat 95%

• Usually operations on Binary Tree can be done both Iteratively(BFS) and Recursively(DFS).

In this case, Iteratively traverse would be simple and clear with Stack.

Reverse odd index row before return.

``````public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;

int cur = 1;
int total = 0;
TreeNode temp = null;
List<Integer> tempList = new ArrayList<Integer>();

while(!q.isEmpty())
{

temp = q.poll();
cur--;
if(temp.left != null)
{
total++;
}
if(temp.right != null)
{
total++;
}
if(cur == 0)
{
cur = total;
total = 0;

tempList = new ArrayList<Integer>();
}
}

for(int i = 1; i < res.size();i+=2)
{
Collections.reverse(res.get(i));
}

return res;
}
}
``````

Recursively:

The key is to remember which level / line / row / floor the current node belongs to, for adding.
pre-order or in-order wont hurt, since node will be added to different level.

``````public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;

helper(res,root,0);

for(int i = 1; i < res.size();i+=2)
{
Collections.reverse(res.get(i));
}

return res;
}

public void helper(List<List<Integer>> res, TreeNode root, int level)
{
if(root == null) return;

List<Integer> tempList = new ArrayList<Integer>();

helper(res,root.left,level+1);
helper(res,root.right,level+1);
}
}
``````

Recursive solution beat 95%, better than Iterative solution. I guess the main reason is I did sh*ty code with Iterative solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.