103 Binary Tree Zigzag Level Order Traversal

Given a binary tree, return thezigzag level ordertraversal 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]
]

Approach:

We can first reduce this problem performing a level order traversal that meet the requirement of allocating a new vector per level. To do this, we follow two conditions. (1) If the element in the queue is null, then push in another nullptr. Here, we also know that the temporary 1d vector has finished its insertions, so it can be pushed back to the main 2d vector, and reset. Additionally, we flip a switch the tells is that the next insertion should be pushed back in reverse order. (2) Otherwise, do the usual bits of adding the left and right nodes.

How it works:

Consider the following tree:

        3
     9     20
 3      15      7
      20  23

We would follow roughly through the following process:

// initialize queue elements
push(3)
push(null)
   ^
top(3)
push children 9 and 20
   ^
top(null)
push(null) // which follows after 9 and 20
   ^
top(9)
push child 3
   ^
top(20)
push children 15 and 7
   ^
top(null)
push(null) // which follows after 3 15 and 7.

As we can see, every null that follows will be appropriate.

Limitations

Pushing back to the front of a vector is a bad idea! Ideally, I would have returned vector of lists.

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> zig_zag_lvl;
    vector<int> v_temp;
    if (!root) return zig_zag_lvl;

    bool insert_back = true;

    queue<TreeNode*> q;
    q.push(root);
    q.push(nullptr);

    while (!q.empty()) {

        TreeNode* cur_top = q.front();
        q.pop();

        if (cur_top) {
            if (insert_back) 
                v_temp.push_back(cur_top->val);
            else 
                v_temp.insert(v_temp.begin(), cur_top->val);

            if (cur_top->left)
                q.push(cur_top->left);
            if (cur_top->right)
                q.push(cur_top->right);
        }

        else {
            if (!q.empty())
                q.push(nullptr);

            zig_zag_lvl.push_back(v_temp);
            v_temp.clear();
            insert_back = !insert_back;
        }
    }

    return zig_zag_lvl;
}