本文共 2099 字，大约阅读时间需要 6 分钟。

题目

解析

层次遍历——翻转记录数组

• 用levelsize记录每层的节点数；
• 用vtmp正常遍历顺序记录每层节点；
• 用flag记录单双层，用于翻转vtmp；
  

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; *///[1,2,3,4,null,null,5]//[3,9,20,null,null,15,7]class Solution {
   public:    vector
   
    
     > zigzagLevelOrder(TreeNode* root) {
           vector
     
      
       > res;        if(root==nullptr)return res;        queue
       
         q;        q.push(root);        int levelsize=q.size();//记录当前层的节点数量        int flag=false;        while(!q.empty()){
               //遍历当前层所有节点            vector
        
          vtmp; while(levelsize--){ TreeNode* ttmp=q.front(); q.pop(); vtmp.push_back(ttmp->val); if(ttmp->left!=nullptr)q.push(ttmp->left); if(ttmp->right!=nullptr)q.push(ttmp->right); } if(flag)reverse(vtmp.begin(),vtmp.end()); res.push_back(vtmp); flag=~flag; levelsize=q.size(); } return res; }};
        
       
      
     
    
   

官方解答——双向队列deque

• 用isOrderLeft记录单双层
• 通过isOrderLeft判断节点添加到levelList的左边还是右边

class Solution {
   public:    vector
   
    
     > zigzagLevelOrder(TreeNode* root) {
           vector
     
      
       > ans;        if (!root) {
               return ans;        }        queue
       
         nodeQueue;        nodeQueue.push(root);        bool isOrderLeft = true;        while (!nodeQueue.empty()) {
               deque
        
          levelList; int size = nodeQueue.size(); for (int i = 0; i < size; ++i) { auto node = nodeQueue.front(); nodeQueue.pop(); if (isOrderLeft) { levelList.push_back(node->val); } else { levelList.push_front(node->val); } if (node->left) { nodeQueue.push(node->left); } if (node->right) { nodeQueue.push(node->right); } } ans.emplace_back(vector
         
          { levelList.begin(), levelList.end()}); isOrderLeft = !isOrderLeft; } return ans; }};/*作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/solution/er-cha-shu-de-ju-chi-xing-ceng-xu-bian-l-qsun/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/