C++ solution , one stack, use stl reversefunction


  • 0
    T
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            
            vector<vector<int>> res;
            if( root == NULL )
                return res;
              
            queue<TreeNode*> nodeQueue;
            vector<int> r;
            
            nodeQueue.push(root);
            nodeQueue.push(NULL); // End Mark;
            
            bool leftFirst = true;
            
            while( !nodeQueue.empty() || !r.empty() )
            {
                TreeNode* top = NULL;
                if( !nodeQueue.empty() )
                {
                    top = nodeQueue.front();
                    nodeQueue.pop();               
                }
                
                if( top == NULL ) // find end mark
                {
                    if( r.empty())
                        break;
                    
                    if(!leftFirst)
                        std::reverse(r.begin(), r.end());
                    
                    res.push_back(r);
                    r.clear();
                    leftFirst = !leftFirst;
                    nodeQueue.push(NULL); // End Mark;
                }
                else
                {
                    r.push_back( top->val );
                    if( top->left != NULL )
                        nodeQueue.push(top->left);
                    if( top->right != NULL )
                        nodeQueue.push(top->right);                
                }
            }
            
            return res;
        }
    };

Log in to reply
 

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