Binary Tree Zigzag Level Order Traversal

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

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

----------------------------------------------------------- thinking ----------------------------------------------------------
the main algorithm is very simple, but there is a bug I need to pay attention to:
when using NULL as the index for level switch, the while loop will return before the last level's result is added into the final result! So the final step should be adding the last one before return.
-------------------------------------------------------------- codes ---------------------------------------------------
class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        bool dir = true;
        queue<TreeNode *> qe;
        qe.push(root);
        qe.push(NULL);
        vector<vector<int>> result;
        vector<int> cur_rslt;
        if (root == NULL) return result;
        while (qe.size() > 1) {
            TreeNode *cur = qe.front();
            qe.pop();
            if (cur == NULL) {
                result.push_back(cur_rslt);
                dir = !dir;
                cur_rslt.resize(0);
                qe.push(NULL);
                continue;
            }
            if (dir) {
                cur_rslt.push_back(cur->val);
            } else {
                cur_rslt.insert(cur_rslt.begin(), cur->val);
            }
            if (cur->left) {
                qe.push(cur->left);
            }
            if (cur->right) {
                qe.push(cur->right);
            }
        }
        if (cur_rslt.size()) {
            //bug here
            //the while will return before the last level's cur_rslt is added into result
            result.push_back(cur_rslt);
        }
        return result;
    }

};

------------------------ two stacks codes ------------------------------------------------------------------------
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int> > res; if (root == NULL) return res; stack<TreeNode*> nodes; nodes.push(root); bool left_to_right = true; while (!nodes.empty()) { stack<TreeNode*> next_nodes; vector<int> cur_values; while (!nodes.empty()) { TreeNode *cur_node = nodes.top(); nodes.pop(); if (cur_node == NULL) continue; cur_values.push_back(cur_node->val); if (left_to_right) { next_nodes.push(cur_node->left); next_nodes.push(cur_node->right); } else { next_nodes.push(cur_node->right); next_nodes.push(cur_node->left); } } if (!cur_values.empty()) res.push_back(cur_values); nodes = next_nodes; left_to_right = !left_to_right; } return res; } };