双端队列解决
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]思路 使用层序遍历的变种，还是使用队列，不过这里我们使用双端队列：
对于从左往右的：队头取元素，队尾压入，压入顺序是先左孩子再右孩子 对于从往左的：队尾取元素，队头压入，压入顺序是先右孩子再左孩子 复杂度 时间复杂度: O(n)O(n)O(n)
空间复杂度: O(logn)O(logn)O(logn)
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
deque<TreeNode*> d;
vector<vector<int>> ans;
if(nullptr == root) return ans;
d.push_back(root);
int count = 1,level = 0;
while(!d.empty()){
int temp = 0;
vector<int> vec;
if(level%2==0){
while(count--){
TreeNode* node = d.front();
d.pop_front();
vec.emplace_back(node->val);
if(node->left){
d.push_back(node->left);
++temp;
}
if(node->right){
d.push_back(node->right);
++temp;
}
}
}else{
while(count--){
TreeNode* node = d.back();
d.pop_back();
vec.emplace_back(node->val);
if(node->right){
d.push_front(node->right);
++temp;
}
if(node->left){
d.push_front(node->left);
++temp;
}
}
}
count = temp;
++level;
ans.push_back(vec);
}
return ans;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-11-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
