[3ms C++] Non-recurrsion solution beat 100%


  • 1
    D

    Simple Queue based by level traverse with help of a "left to right" flag.

    class Solution {
    public:
        vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
            vector<vector<int>> result;
            if (root == NULL) {
                return result;
            }
            
            queue<TreeNode*> q;
            q.push(root);
            bool l2r = true;  // left to right
    
            while (!q.empty()) {
                vector<int> v;
                int size = q.size();
                for (size_t i = 0; i < size; i++) {
                    TreeNode * node = q.front();
                    q.pop();
    
                    v.push_back(node->val);
    
                    if (node->left != NULL) {
                        q.push(node->left);
                    }
    
                    if (node->right != NULL) {
                        q.push(node->right);
                    }
                }
                
                if (!l2r) {
                    reverse(v.begin(), v.end());
                }
    
                result.push_back(v);
                l2r = !l2r;
            }
    
            return result;
        }
    };
    

Log in to reply
 

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