levelOrder tree traversal with JavaScript using Queue


  • 0
    N
    const Queue = function() {
        this._storage = {};
        this._addIndex = 0;
        this._removeIndex = 0;
    };
    
    Queue.prototype.queue = function(value) {
        this._storage[++this._addIndex] = value;
    };
    
    Queue.prototype.dequeue = function() {
        if(this.size()) {
            let removed = this._storage[++this._removeIndex];
            delete this._storage[this._removeIndex];
            return removed;
        }
    };
    
    Queue.prototype.size = function() {
        return this._addIndex - this._removeIndex;
    };
    
    
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number[][]}
     */
    var levelOrder = function(root) {
        let response = [];
        
        let q = new Queue();
        
        if(root) {
            root.level = 0;
            q.queue(root);
        }
        
        while(q.size()) {
            let e = q.dequeue();
            
            response[e.level] = response[e.level]  || [];
            response[e.level].push(e.val);
            
            if(e.left) {
                e.left.level = e.level + 1;
                q.queue(e.left);
            }
            
            if(e.right) {
                e.right.level = e.level + 1;
                q.queue(e.right);
            }
        }
        
        return response;
    };
    

Log in to reply
 

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