此题难度在于如何标记每一层的末尾节点。
思路1:队列层次遍历，遇到偶数层末尾反转一下数组
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
int t;
vector<int> tmp;
deque<TreeNode*> deq;
deq.push_back(root);
TreeNode* p,*tail=root;//tail记录每一层的最后一个结点
bool isEven=true; //当前遍历到的层数是奇数层，就从左到右遍历
while(!deq.empty()){
p=deq.front();
tmp.push_back(p->val);
deq.pop_front();
if(p->left) deq.push_back(p->left);
if(p->right) deq.push_back(p->right);
if(p==tail){ //遍历完一层
tail=deq.back();
if(!isEven){ //交换vector位置
int l=tmp.size();
for(int i=;i<l/;i++){
t=tmp[l--i];
tmp[l--i]=tmp[i];
tmp[i]=t;
}
}
res.push_back(tmp);
isEven=!isEven;
tmp.clear();
}
}
return res;
}
};
思路2：双栈
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(root ==NULL)return {};
stack<TreeNode*> s;
stack<TreeNode*> q;
int flag = ;//使用哪个栈
vector<vector<int>> res;
s.push(root);
while(!s.empty() || !q.empty())
{
if(flag == )
{
vector<int> v_t;
flag = ;
while(!s.empty())
{
TreeNode* tmp = s.top();s.pop();
v_t.push_back(tmp->val);
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
if(v_t.size()>) res.push_back(v_t);
}
else
{
vector<int> v_t;
flag = ;
while(!q.empty())
{
TreeNode* tmp = q.top();q.pop();
v_t.push_back(tmp->val);
if(tmp->right) s.push(tmp->right);
if(tmp->left) s.push(tmp->left);
}
if(v_t.size()>) res.push_back(v_t);
}
}
return res;
}
};