leetcode 103:二叉树的锯齿形层次遍历
二叉树的问题,这个题我选择使用队列来做,两个队列,可能方法比较笨
std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
std::vector<std::vector<int>>a;
std::deque<TreeNode*>q1;
std::deque<TreeNode*>q2;
std::vector<int>v;
int i=1;
if(root==NULL)return a;
q1.push_back(root);
while(!q1.empty()||!q2.empty()){
if(i%2==1){
while(!q1.empty()){
TreeNode*p=q1.front();
q1.pop_front();
if(p->left!=NULL)q2.push_back(p->left);
if(p->right!=NULL)q2.push_back(p->right);
v.push_back(p->val);
}
}
if(i%2==0){
while(!q2.empty()){
TreeNode*p=q2.back();
q2.pop_back();
if(p->right!=NULL)q1.push_front(p->right);
if(p->left!=NULL)q1.push_front(p->left);
v.push_back(p->val);
}
}
a.push_back(v);
v.clear();
i++;
}
return a;
}