迭代

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

vector<vector<int>> ret;

if(root == nullptr) return ret;

queue<TreeNode*> cur,nxt;

TreeNode* p;

cur.push(root);

vector<int> level;

int order;

while(!cur.empty()){

order=ret.size();

while(!cur.empty()){

p = cur.front();

cur.pop();

if(order%2>0)

level.insert(level.begin(),p->val);

else

level.push_back(p->val);

if(p->left) nxt.push(p->left);

if(p->right) nxt.push(p->right);

}

ret.push_back(level);

level.clear();

swap(cur,nxt);

}

return ret;

}