# My AC Java code

• I use two stacks, one for processing current layer and one for storing nodes for the next layer. I also use a flag (order in your code) to indicate the direction. It is straightforward

``````public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> output = new ArrayList<List<Integer>>();
if (root == null) return output;
Stack<TreeNode> cur_layer = new Stack<TreeNode>(); cur_layer.push(root);
Stack<TreeNode> next_layer = new Stack<TreeNode>();
List<Integer> layer_output = new ArrayList<Integer>();
int d = 0; // 0: left to right; 1: right to left.

while (!cur_layer.isEmpty()){
TreeNode node = cur_layer.pop();
layer_output.add(node.val);
if(d==0){
if (node.left != null) next_layer.push(node.left);
if (node.right != null) next_layer.push(node.right);
}else{
if (node.right != null) next_layer.push(node.right);
if (node.left != null) next_layer.push(node.left);
}

if (cur_layer.isEmpty()){
output.add(layer_output);
layer_output = new ArrayList<Integer>();
cur_layer = next_layer;
next_layer = new Stack<TreeNode>();;
d ^= 1;
}
}
return output;
}``````

• You can use output size to figure out d, Actually, d = output.size() % 2, so one less thing to wrong about.

• Steps for solution:

Create an empty stack s and push root to it.

while stack is not NULL Do following:-

• Create a empty stack called tempStack.

• Pop a node from stack and push it to tempStack depending on directionFlag.

• Change directionFlag to change the direction of traversal.

• set stack=tempStack.

``````  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

List<List<Integer>> result=new ArrayList<List<Integer>>();
Stack<TreeNode> stack=new Stack<TreeNode>();

if(root==null) return result;

stack.push(root);

boolean directionflag=false;
while(!stack.isEmpty())
{
List<Integer> arr = new ArrayList<>();
Stack<TreeNode> tempStack=new Stack<TreeNode>();

while(!stack.isEmpty())
{

TreeNode tempNode=stack.pop();
arr.add(tempNode.val);

if(!directionflag)
{
if(tempNode.left!=null)
tempStack.push(tempNode.left);
if(tempNode.right!=null)
tempStack.push(tempNode.right);

}else
{
if(tempNode.right!=null)
tempStack.push(tempNode.right);
if(tempNode.left!=null)
tempStack.push(tempNode.left);
}

}
// for changing direction
directionflag=!directionflag;
stack=tempStack;

result.add(arr);
}
return result;

}``````

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