# 103 - Binary Tree Zigzag Level Order Traversal

解法一 - 用 vector 存各層結果，單數層要先 reverse 再放進答案

/**
 * Definition for a binary tree node.
 * 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) return res;

        vector<TreeNode*> cur;
        vector<TreeNode*> next;
        cur.push_back(root);
        int level = 0;

        while(!cur.empty()) {       
            vector<int> tmp;

            for (vector<TreeNode*>::iterator it = cur.begin() ; it != cur.end(); ++it) {
                if((*it)->left) next.push_back((*it)->left);
                if((*it)->right) next.push_back((*it)->right);
                tmp.push_back((*it)->val);
            }

            if(level%2 == 1) {
                reverse(tmp.begin(), tmp.end());
            }

            res.push_back(tmp);
            level++;
            cur = next;
            next.clear();
        }

        return res;
    }
};

// idea: when in even level, output normally; when in odd level, reverse before push to ans

Runtime: 4 ms, faster than 88.61% of C++ online submissions for Binary Tree Zigzag Level Order Traversal. Memory Usage: 13.4 MB, less than 92.60% of C++ online submissions for Binary Tree Zigzag Level Order Traversal.

解法二 - 用兩個 stack，處理第二個 stack 時要從 right child 開始塞

實作如下：

/**
 * Definition for a binary tree node.
 * 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) return res;

        stack<TreeNode*> even;
        stack<TreeNode*> odd;
        even.push(root);

        while(!even.empty() || !odd.empty()) {       
            vector<int> tmp;

            while(!even.empty()) {
                TreeNode* cur = even.top();
                even.pop();
                tmp.push_back(cur->val);

                if(cur->left) odd.push(cur->left);
                if(cur->right) odd.push(cur->right);
            }

            res.push_back(tmp);
            tmp.clear();

            while(!odd.empty()) {
                TreeNode* cur = odd.top();
                odd.pop();
                tmp.push_back(cur->val);

                if(cur->right) even.push(cur->right);
                if(cur->left) even.push(cur->left);
            }

            if(!tmp.empty()) res.push_back(tmp);
        }

        return res;
    }
};

Runtime: 4 ms, faster than 88.61% of C++ online submissions for Binary Tree Zigzag Level Order Traversal. Memory Usage: 13.3 MB, less than 98.21% of C++ online submissions for Binary Tree Zigzag Level Order Traversal.