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

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    vector<vector<int> > result;
    preOrder(root, 0, result);

    size_t size = result.size();
    for (size_t i = 1; i < size; i+=2) {
        size_t jSize = result[i].size();
        for (size_t j = 0; j < jSize/2; ++j) {
            int tmp = result[i][j];
            result[i][j] = result[i][jSize-1-j];
            result[i][jSize-1-j] = tmp;
        }
    }

    return result;
}

void preOrder(TreeNode *n, int level, vector<vector<int> > &result) {
    if (n == NULL) return;

    if (level >= result.size()) {
        result.resize(level+1);
    }

    result[level].push_back(n->val);

    preOrder(n->left, level+1, result);
    preOrder(n->right, level+1, result);
}