同样是用队列维护,但是多用了一个栈用来反转。
class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode* root) { vector<vector<int> > vec; if(root == nullptr) return vec; queue<TreeNode*> que; int flag = 0; que.push(root); while(!que.empty()) { int len = que.size(); vector<int> tempVec; stack<int> stk; for(int i = 0; i < len; i++) { TreeNode *temp = que.front(); if(temp->left != nullptr) que.push(temp->left); if(temp->right != nullptr) que.push(temp->right); if(flag % 2) stk.push(temp->val); else tempVec.push_back(temp->val); que.pop(); } if(flag % 2) while(!stk.empty()) { tempVec.push_back(stk.top()); stk.pop(); } vec.push_back(tempVec); flag++; } return vec; } };