题解 | #二叉树的之字形层序遍历#

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        if(root == NULL)
            return {};
        else{
                vector<TreeNode*> s;
                vector<vector<int>> t;
                int depth=0,front=-1,rear=-1,last=0;
                s.emplace_back(root);
                rear++;
                while(front < last)
                {
                    if(depth%2 == 0)
                    {
                        int f=front;  //临时变量
                        t.resize(depth+1);
                        //将元素入队列,从左向右
                        while(f<last)
                        {
                            f++;
                            t[depth].emplace_back(s[f]->val);
                        }
                        //将树节点入队列
                        while(front < last)
                        {
                            front++;
                            if(s[front]->left)
                            {
                                s.emplace_back(s[front]->left);
                                rear++;
                            }
                            if(s[front]->right)
                            {    
                                s.emplace_back(s[front]->right);
                                rear++;
                            }
                        }
                        last=rear;  //二叉树最右结点
                    }
                    else
                    {
                        int f=front;
                        int l=last;
                        t.resize(depth+1);
                        //将元素入队列,从右向左
                        for(int i=last;i>front;i--)
                            t[depth].emplace_back(s[i]->val);
                        //将树节点入队列
                        while(front<last)
                        {
                            front++;
                            if(s[front]->left)
                            {
                                s.emplace_back(s[front]->left);
                                rear++;
                            }
                            if(s[front]->right)
                            {    
                                s.emplace_back(s[front]->right);
                                rear++;
                            }
                        }
                    }
                    last=rear; //last指向最右结点下标
                    depth++;  //深度+1
                }
            return t;
            }    
    }
};