力扣 103. 二叉树的锯齿形层序遍历 [内存优化]

 class Solution {
public:
    void work(vector<vector<int>>& vec,TreeNode *p,int cnt){//int记录当前层数
        if(p==nullptr)
            return;
        if(cnt>=vec.size())//如果层数比size大，说明是新的一层
        {
            vector<int> tmp;
            tmp.push_back(p->val);
            vec.push_back(tmp);
        }
        else{//原有的一层，直接访问更新
            vec[cnt].push_back(p->val);
        }
        work(vec,p->right,cnt+1);
        work(vec,p->left,cnt+1);    
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        work(res,root,0);
        for(int i=2;i<res.size();i+=2){//reverse需要翻转的部分
            reverse(res[i].begin(),res[i].end());
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==nullptr){
            return res;
        }
        bool ifReverse=false;//标志位：是否翻转当前层
        queue<TreeNode*> que;//存放每一层的节点
        que.push(root);
        while(!que.empty()){
            int len=que.size();
            deque<int> layer;//记录每一层的节点
            for(int i=0;i<len;i++){//处理当前层的节点
                TreeNode * cur=que.front();//取出当前层的一个节点
                que.pop();
                //处理此节点：记录val和处理左右子节点
                if(ifReverse)//当前层需要翻转，就利用deque，从头部放入，实现逆序
                    layer.push_front(cur->val);
                else
                    layer.push_back(cur->val);//正序
                //放入子节点，还是先左后右的顺序
                if(cur->left)
                    que.push(cur->left);
                if(cur->right)
                    que.push(cur->right);
            }
            ifReverse=!ifReverse;//每层处理结束,标志位更新
            res.emplace_back((vector<int>){layer.begin(),layer.end()});//放入每层的节点值
        }
        return res;
    }
};

 /**
 * 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) {
        vector<vector<int>> res;
        if(root==nullptr){
            return res;
        }
        queue<TreeNode*> que;//存放每一层的节点
        que.push(root);
        bool ifReverse=false;//标志位：是否翻转当前层
        int len;
        while(!que.empty()){
            len=que.size();
            int *layer = new int[len];//记录每一层的节点，使用int数组
            for(int i=0;i<len;i++){//处理当前层的节点
                TreeNode * cur=que.front();//取出当前层的一个节点
                que.pop();
                //处理此节点：记录val和处理左右子节点  
                layer[ifReverse ? len -i - 1 : i] = cur -> val;//根据标志位确定放入正序还是逆序
                //放入子节点，还是先左后右的顺序
                if(cur->left)
                    que.push(cur->left);
                if(cur->right)
                    que.push(cur->right);
            }
            ifReverse=!ifReverse;//每层处理结束,标志位更新
            res.emplace_back((vector<int>){layer,layer+len});//将int数组转化为vector
        }
        return res;
    }
};