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).

BinaryTreeZigzagLevelOrderTraversal.cpp

/*
Binary Tree Zigzag Level Order Traversal::

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
https://www.interviewbit.com/problems/zigzag-level-order-traversal-bt/

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).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]
*/

//solution 1 :using two stacks , time - O(n) ,space - O(n)
vector<vector<int> > zigzagLevelOrder(TreeNode* A) {
    vector<vector<int> > res ;
    if(!A) return res ;
    
    vector<int> visit ;
    stack<TreeNode* > st1 ;
    stack<TreeNode* > st2 ;
    st1.push(A) ;
    while(!st1.empty() || !st2.empty())
    {
        visit.clear() ;   
        while(!st1.empty())
        {
            TreeNode* temp = st1.top() ;
            st1.pop() ;
            visit.push_back(temp->val) ;
            if(temp->left != NULL) st2.push(temp->left) ;
            if(temp->right != NULL) st2.push(temp->right) ;
        }
        if(!visit.empty()) res.push_back(visit) ;

        visit.clear() ;   
        while(!st2.empty())
        {
            TreeNode* temp = st2.top() ;
            st2.pop() ;
            visit.push_back(temp->val) ;
            if(temp->right != NULL) st1.push(temp->right) ;
            if(temp->left != NULL) st1.push(temp->left) ;
        }
        if(!visit.empty()) res.push_back(visit) ;
    }
    
    return res ;
}

//solution 2 :using one queue , time - O(n) ,space - O(n)
//here if(count % 2 == 0 ) then take the order from left to right 
//otherwise take the from right to left 
	vector<vector<int> > zigzagLevelOrder(TreeNode* A) {
    vector<vector<int> > res ;
    if(A==NULL)  return res;
    queue<TreeNode* > que;
    que.push(A);
    int count=0;
    while(!que.empty()){
        vector<int> tmp;
        int curSize=que.size();
        for(int i=0;i<curSize;i++){
            TreeNode* temp_front = que.front() ; que.pop() ;
            
            if(temp_front->left!=NULL) que.push(temp_front->left);
            if(temp_front->right!=NULL) que.push(temp_front->right);
                
            tmp.push_back(temp_front->val);
        }
		// here order is only reverse when condition it true 
		// ie take the order from right to left
        if(count%2!=0) 
            reverse(tmp.begin() , tmp.end()) ;
        res.push_back(tmp);
        count++;
    }
    return res;
	}
	
//using simple dfs 
//create vector when you visit the level for first time
//if(level%2==0) push_back in vector 
//otherwise push_front to maintain zig zag order .
class Solution {
public:
    void travel(TreeNode* cur, vector<vector<int>> &res, int level) {
        if (cur == NULL)    return;
        
        if (res.size() <= level) {
            vector<int> newLevel;
            res.push_back(newLevel);
        }
        
        if (level % 2 == 0)
            res[level].push_back(cur->val);
        else
            res[level].insert(res[level].begin(), cur->val); // this operation is O(n) , costly operation
        
        travel(cur->left, res, level+1);
        travel(cur->right, res, level+1);
    }

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        travel(root, res, 0);
        return res;
    }
};