#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cstring>
#include<cassert>
#include<climits>
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<algorithm>
#include<iterator>
#include<string>
#include<tuple>
#include<random>
#include <chrono>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void zigzag(TreeNode* root) {
    vector<TreeNode*> pts;
    if (NULL == root)
        return;
    queue<TreeNode*> q;
    q.push(root);
    int num1 = 1, num2 = 0;
    TreeNode* cur = NULL;
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        if (cur->left != NULL) {
            q.push(cur->left);
            num2++;
        }
        if (cur->right != NULL) {
            q.push(cur->right);
            num2++;
        }
        pts.push_back(cur);
        num1--;
        if (0 == num1) {
            pts.push_back(NULL);
            num1 = num2;
            num2 = 0;
        }
    }
    int n = pts.size();
    int rev = 0;
    int i, j;
    i = -1;
    int mid, sum;
    while (i < n) {
        j = i + 1;
        while (j < n && pts[j] != NULL)
            j++;
        // reverse
        if (rev) {
            mid = i + (j - i) / 2;
            sum = i + j;
            for (int x=i+1; x<=mid; x++)
                swap(pts[x], pts[sum-x]);
        }
        rev = !rev;
        i = j;
    }
    for (i=0; i<n; i++)
        if (pts[i] != NULL)
            printf(" %d ", pts[i]->val);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(6);
    zigzag(root);
    return 0;
}

用普通的队列加标记即可实现。