3ms C++ solution using deque


  • 0
    K
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
        {
    
            vector<vector<int>> result;
            
            if(root==nullptr)
                return result;
            
            list<TreeNode*> q;
            q.push_back(root);
            bool flag = true;
            while(!q.empty())
            {
                int nodeCount = q.size();
                vector<int> levelNodes;
                // Print left to right
                if(flag)
                {
                    while(nodeCount--)
                    {
                        TreeNode* frontNode = q.front();
                        q.pop_front();
                        
                        levelNodes.push_back(frontNode->val);
                        
                        if(frontNode->left)
                            q.push_back(frontNode->left);
                    
                        if(frontNode->right)
                            q.push_back(frontNode->right);
                    }
                }
                else
                {
                    while(nodeCount--)
                    {
                        TreeNode* frontNode = q.back();
                        q.pop_back();
                        
                        levelNodes.push_back(frontNode->val);
                        
                        if(frontNode->right)
                            q.push_front(frontNode->right);
                        
                        if(frontNode->left)
                            q.push_front(frontNode->left);
                    }
                }
                
                result.push_back(levelNodes);
                flag = !flag;
            }
            return result;
        }
    };
    

Log in to reply
 

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