Binary Tree Zigzag Level Order Traversal

LeetCode #103

Description:

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

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]
]

Idea:

与binary tree level order traversal几乎一样，只需要额外设置bool的flag，确定学不需要reverse每一层。

Code:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q_curr, q_next;
        vector<int> level;
        vector<vector<int>> result;
        TreeNode * node;
        bool flag_reverse=false; // extra flag to determine reverse or not
        if(root!=NULL) q_curr.push(root);

        while(!q_curr.empty()){
            while(!q_curr.empty()){
                node=q_curr.front();
                q_curr.pop();

                level.push_back(node->val);
                if(node->left!=NULL) q_next.push(node->left);
                if(node->right!=NULL) q_next.push(node->right);
            }
            swap(q_curr, q_next);
            // reverse level vector if necessary 
            if(flag_reverse) reverse(level.begin(), level.end()); 
            flag_reverse = !flag_reverse; // Change flag
            result.push_back(level);
            level.clear();
        }

        return result;
    }
};