Leetcode103 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

提示：

• 树中节点数目在范围 $[0,2000]$ 内
• -100 <= Node.val <= 100

题解1 层序遍历+双向队列

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(! root ) return vector<vector<int>>();deque<TreeNode*> dq;dq.push_back(root);int level = 0;vector<vector<int>> ret;while(dq.size()){int s = dq.size();int flag = level % 2;vector<int> res;while(s --){TreeNode* tmp = nullptr;if(! flag){tmp = dq.front();res.emplace_back(tmp->val);dq.pop_front();// 队列if(tmp->left) dq.push_back(tmp->left);if(tmp->right) dq.push_back(tmp->right);}else{tmp = dq.back();res.emplace_back(tmp->val);dq.pop_back();// 相当于栈if(tmp->right) dq.push_front(tmp->right);if(tmp->left) dq.push_front(tmp->left);}}level++;ret.emplace_back(res);}return ret;}
};