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).
Example :
Given binary tree
3
/ \
9 20
/ \
15 7
return
[
[3],
[20, 9],
[15, 7]
]
// pop all values from left stack and push to right stack
Example :
Given binary tree
3
/ \
9 20
/ \
15 7
return
[
[3],
[20, 9],
[15, 7]
]
Explanation : This problem i am solving using two stack, first stack will rotate left to right and another stack right to left so in one stack will push value from first right then left, and in another one first left then right. And at last adding all those to a list .
ll is temporary list that will be created every time will go inside while loop and once out from while it will be added to another result list.
public class Solution {
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode A) {
if(A == null)return null;
ArrayList<ArrayList<Integer>> list = new ArrayList();
ArrayList<Integer> ll = null;
Stack<TreeNode> leftStack = new Stack();
Stack<TreeNode> rightStack = new Stack();
leftStack.push(A);
while(!leftStack.isEmpty() ){
// pop all values from left stack and push to right stack
while(!leftStack.isEmpty()){
ll = new ArrayList();
int n = leftStack.size();
for(int i=0;i<n;i++){
TreeNode temp = leftStack.pop();
ll.add(temp.val);
if(temp.left != null){
rightStack.push(temp.left);
}
if(temp.right != null){
rightStack.push(temp.right);
}
}
if(!ll.isEmpty())list.add(ll);
}
// pop all values from right stack and push to left stack
while(!rightStack.isEmpty()){
ll = new ArrayList();
int n = rightStack.size();
for(int i=0;i<n;i++){
TreeNode temp = rightStack.pop();
ll.add(temp.val);
if(temp.right != null){
leftStack.push(temp.right);
}
if(temp.left != null){
leftStack.push(temp.left);
}
}
if(!ll.isEmpty())list.add(ll);
}
}
return list;
}
}