给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ 9 20
/ 15 7
返回锯齿形层次遍历如下：
[ [3], [20,9], [15,7] ]
每层的队列正常处理，隔一行计算结果时反转加入结果数组
1 class Solution:
2 def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
3 res=[]
4 if not root:
5 return res
6 stack=[root]
7 count=0
8 while stack:
9 res.append([])
10 l=len(stack)
11 for i in range(l):
12 res[-1].append(stack[i].val)
13 if stack[i].left:
14 stack.append(stack[i].left)
15 if stack[i].right:
16 stack.append(stack[i].right)
17 if count==1:
18 res[-1].reverse()
19 count=0
20 else:
21 count=1
22 stack=stack[l:]
23 return res
但这样的时间复杂度比较大，因为reverse操作比较费时。
利用双端队列，队列中顺序始终是正常的，但奇数行从右向左遍历，pop右边的，孩子push进左边。偶数行从左向右遍历，pop左边的，孩子push进右边。
1 class Solution {
2 public:
3 vector<vector<int> > Print(TreeNode* pRoot) {
4 if(pRoot==nullptr){return {};}
5 deque<TreeNode*> my_queue;
6 my_queue.push_back(pRoot);
7 vector<vector<int>>res;
8 int cnt=0;
9 while(not my_queue.empty()){
10 res.push_back({});
11 int cur_siz=my_queue.size();
12 decltype(pRoot) cur;
13 for(int i=0;i<cur_siz;++i){
14 if(cnt&1){
15 cur=my_queue.back();
16 my_queue.pop_back();
17 if(cur->right){
18 my_queue.push_front(cur->right);
19 }
20 if(cur->left){
21 my_queue.push_front(cur->left);
22 }
23 }
24 else{
25 cur=my_queue.front();
26 my_queue.pop_front();
27 if(cur->left){
28 my_queue.push_back(cur->left);
29 }
30 if(cur->right){
31 my_queue.push_back(cur->right);
32 }
33 }
34 res.back().push_back(cur->val);
35 }
36 ++cnt;
37 }
38 return res;
39 }
40 };
用两个栈模拟队列（普通队列）。题解看见的思路，很有意思：两个栈，比如1、3、5行存栈1里，2、4、6存栈2里，栈1每次pop时，左右孩子分别push进栈2，这样栈1中的栈顶元素的左右孩子在栈2的栈底，栈1中的栈底元素的左右孩子在栈2的栈顶，再对栈2pop，pop的左右孩子再push进栈1，就这样交错push/pop。其实就是用两个栈模拟队列，算法导论上看过，不过这里能活学活用还是挺有意思的。
代码很容易，直接把人家代码粘来了，人家的题解地址：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/solution/liang-ge-stackde-jie-fa-bu-xu-fan-zhuan-queuehuo-z
1 vector<vector<int>> zigzagLevelOrder(TreeNode *root) { 2 //右往左时右先入栈，左往右时，左先入栈。然后要两个栈分别保存每一层级的。 3 //这里借鉴了树的层次遍历的思想，不过那是用队列 4 vector<vector<int>> r; 5 if (!root) return r; 6 stack<TreeNode *> d1, d2; 7 d1.push(root); 8 TreeNode *curr = nullptr; 9 vector<int> tmp; 10 while (true) { 11 while (!d1.empty()) { 12 curr = d1.top(); 13 d1.pop(); 14 tmp.push_back(curr->val); 15 if (curr->left) d2.push(curr->left); 16 if (curr->right) d2.push(curr->right); 17 } 18 if (!tmp.empty()) { 19 r.push_back(tmp); 20 tmp.clear(); 21 } else break; 22 23 while (!d2.empty()) { 24 curr = d2.top(); 25 d2.pop(); 26 tmp.push_back(curr->val); 27 if (curr->right) d1.push(curr->right); 28 if (curr->left) d1.push(curr->left); 29 } 30 if (!tmp.empty()) { 31 r.push_back(tmp); 32 tmp.clear(); 33 } else break; 34 } 35 return r; 36 };
原文：https://www.cnblogs.com/FdWzy/p/12288152.html