9.Binary Tree Zigzag Level Order Traversal

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

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 I: (Using Two Stacks)

class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root)
    {

        vector<vector<int>> res;

        if (root == NULL)
        {
            return res;
        }
        
        stack<TreeNode *> s1;
        stack<TreeNode *> s2;
        s1.push(root);
        TreeNode *t = NULL;
        
        while (!s1.empty() || !s2.empty())
        {

            vector<int> v1;
            while (!s1.empty())
            {
                t = s1.top();
                s1.pop();
                v1.push_back(t->val);
                if (t->left)
                {
                    s2.push(t->left);
                }

                if (t->right)
                {
                    s2.push(t->right);
                }
            }
            if (v1.size() > 0)
            {
                res.push_back(v1);
            }

            vector<int> v2;
            while (!s2.empty())
            {
                t = s2.top();
                s2.pop();
                v2.push_back(t->val);

                if (t->right)
                {
                    s1.push(t->right);
                }

                if (t->left)
                {
                    s1.push(t->left);
                }
            }
            if (v2.size() > 0)
            {
                res.push_back(v2);
            }
        }

        return res;
    }
};

Time Complexity: O(n) Space Complexity: O(n)+(n)=O(n)