ZigZag Traversal Of Binary Tree

ZigZagTraversal.java

 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode A) {
        
        Queue<TreeNode> q = new LinkedList<>();
        if(A == null) return null;
        
        Stack<TreeNode> currentLevel = new Stack<>();
        Stack<TreeNode> nextLevel = new Stack<>();
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        currentLevel.push(A);
        boolean ltr = true;
        
        ArrayList<Integer> tempList = null;
        while(!currentLevel.isEmpty()){
            TreeNode temp = currentLevel.pop();
            
            q.add(temp);
            
            if(ltr){
                if(temp.left != null){
                    nextLevel.push(temp.left);
                }
                if(temp.right != null){
                    nextLevel.push(temp.right);
                }
            }else{
                if(temp.right != null){
                    nextLevel.push(temp.right);
                }
                if(temp.left != null){
                    nextLevel.push(temp.left);
                }
            }
            
            if(currentLevel.isEmpty()){
                ltr = !ltr;
                Stack<TreeNode> te = currentLevel;
                currentLevel = nextLevel;
                nextLevel = te;
                
                tempList = new ArrayList<Integer>();
                while(!q.isEmpty()){
                    tempList.add(q.remove().val);    
                }
                result.add(tempList);
            }
        }
        
        return result;
        
    }