My c++ solution, simply 4ms AC, using a queue


  • 0
    L
      class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> v;
            queue<TreeNode*> q;
            if(root==NULL)
                return v;
            vector<int> vv;
            vv.push_back(root->val);
            v.push_back(vv);
            vv.pop_back();
            if(root->left!=NULL)
                q.push(root->left);
            if(root->right!=NULL)
                q.push(root->right);
            q.push(root);
            TreeNode* t;
            bool b=true;
            while(!q.empty())
            {
                t=q.front();
                q.pop();
                if(t==root)
                {
                    if(!q.empty())
                        q.push(t);
                    if(b)
                        reverse(vv.begin(),vv.end());
                    if(vv.size()!=0)
                        v.push_back(vv);
                    while(vv.size()!=0)
                        vv.pop_back();
                    b=!b;
                }
                else
                {
                    vv.push_back(t->val);
                    if(t->left!=NULL)
                        q.push(t->left);
                    if(t->right!=NULL)
                        q.push(t->right); 
                }
            }
            return v;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.