Loop Binary Tree Solution - Binary Tree Zigzag Level Order Traversal

The idea is to use two stacks to process each level. one by the other one… notice that one loads from left to right, and the order loads from right to left. A flag is required for condition.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> leftStack = new Stack<TreeNode>();
Stack<TreeNode> rightStack = new Stack<TreeNode>();
leftStack.push(root);
boolean leftRightFlag = true;
while (!(leftStack.isEmpty() && rightStack.isEmpty())) {
TreeNode curProcessing;
if (leftRightFlag) {
curProcessing = leftStack.pop();
result.add(curProcessing.val);
if (curProcessing.left != null) {
rightStack.push(curProcessing.left);
}
if (curProcessing.right != null) {
rightStack.push(curProcessing.right);
}
if (leftStack.isEmpty()) {
results.add(result);
result = new ArrayList<Integer>();
leftRightFlag = false;
}
} else {
curProcessing = rightStack.pop();
result.add(curProcessing.val);
if (curProcessing.right != null) {
leftStack.push(curProcessing.right);
}
if (curProcessing.left != null) {
leftStack.push(curProcessing.left);
}
if (rightStack.isEmpty()) {
results.add(result);
result = new ArrayList<Integer>();
leftRightFlag = true;
}
}
}
return results;
    }
}