https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
题目解析：zigzag遍历就是上一次遍历的最后一个节点的最后一个子节点就是下一次遍历的第一个节点，如果是从左往右遍历，最后一个子节点就是最后一个节点的右节点，如果从右往左遍历，最后一个子节点就是最后一个节点的左节点。从这描述里就看出了有了后进先出的意思，所以可以用栈来存储。用dist来决定子节点的存储顺序，奇数层子节点从左往右存，偶数层子节点从右往左存。 时间复杂度o(n)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root)
{
if(root == NULL) return {} ;
stack<TreeNode*> s ;
vector<vector<int>> res ;
int dist = 0 ;
s.push(root) ;
while(!s.empty())
{
dist++ ;
stack<TreeNode*> ns ;
vector<int> traver ;
while(!s.empty())
{
TreeNode* node = s.top() ;
s.pop() ;
traver.push_back(node->val) ;
if(dist % 2)
{
if(node->left) ns.push(node->left) ;
if(node->right) ns.push(node->right) ;
}
else
{
if(node->right) ns.push(node->right) ;
if(node->left) ns.push(node->left) ;
}
}
res.push_back(traver) ;
s = ns ;
}
return res ;
}
};
解法二：一律按从左往右遍历和存储子节点，但是用flag判断是从左往右存储还是从右往左存储。用queue来存储，时间复杂度o(n)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root)
{
if(root == NULL) return {};
vector<vector<int>> res ;
queue<TreeNode*> q ;
q.push(root) ;
int flag = 0 ;
while(!q.empty())
{
int len = q.size() ;
vector<int> tmp(len) ;
for(int i = 0 ; i < len ; i++)
{
TreeNode* node = q.front() ;
q.pop() ;
//将node的子节点push到q中
if(node->left) q.push(node->left) ;
if(node->right) q.push(node->right) ;
//flag为1，将node的值从右往左放到vector中 ， falg为0，将node的值从左往右放到vector中，q中统一为从左往右遍历
if(flag) tmp[len - i - 1] = node->val ;
else tmp[i] = node->val ;
}
flag ^= 1 ;
res.push_back(tmp) ;
}
return res ;
}
};
leetcode 103. Binary Tree Zigzag Level Order Traversal
原文：https://www.cnblogs.com/mychen06/p/12629100.html