leetcode103. 二叉树的锯齿形层序遍历，简单易懂附代码详解

leetcode103. 二叉树的锯齿形层序遍历

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

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

其实我们可以把这题变得很简单，如果你会做二叉树的层序遍历的话。如果不会，可以先去看看我写的二叉树层序遍历的题解。

如果学会二叉树的层序遍历方法的话，那么这题你就可以把它当作偶数层从左往右遍历，奇数层从右往左遍历，加一个栈暂时存储一层数据。

数据结构选择：使用队列queue来实现广度优先搜索（BFS），用于逐层访问二叉树的节点。对于奇数层，使用栈stack来反转节点的访问顺序。

初始化：首先检查根节点是否为空，如果为空，则直接返回空的二维向量。

层次遍历：将根节点加入队列，然后进入一个循环，直到队列为空，即所有节点都被访问过。

层级计数：使用变量n来记录当前正在访问的层级。

偶数层处理：
计算当前层的节点数。
使用队列来按顺序访问当前层的所有节点，将节点值添加到临时向量temp中。
同时，将当前节点的左右子节点（如果存在）加入队列，以便下一轮访问。

奇数层处理：
与偶数层类似，首先计算当前层的节点数。
但是，这里使用栈来存储节点值，然后从栈中弹出元素并添加到temp中，这样可以反转节点的访问顺序。

具体代码如下：

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    queue<TreeNode*> q;
    vector<vector<int>> res;
    if(!root) return res;
    int n=0;
    q.push(root);
    while(!q.empty())
    {
        int size=q.size();
       vector<int> temp;
        if(n%2==0)
      {  for(int i=0;i<size;i++)
        {
           TreeNode* u=q.front();
           q.pop();
           temp.push_back(u->val);
           if(u->left!=NULL)
           {
             q.push(u->left);
           }
           if(u->right!=NULL)
           { 
             q.push(u->right);
           }
        }
        res.push_back(temp);
        n++;
      }
      else
      {
          stack<int> t;
          for(int i=0;i<size;i++)
        {
           TreeNode* u=q.front();
           q.pop();
           t.push(u->val);
           if(u->left!=NULL)
           {
             q.push(u->left);
           }
           if(u->right!=NULL)
           { 
             q.push(u->right);
           }
        }
        while(!t.empty())
        {
            temp.push_back(t.top());
            t.pop();
        }
        n++;
        res.push_back(temp);
      }
    }
    return res;
    }
};