JavaScript BFS Solution


  • 0
    /*
        BFS
        keep track of the levels
        store level values in a map
        push items to a queue but keep track of the next levels
        
    */
    
    
    var levelOrder = function(root) {
        if(!root){
            return [];
        }
        
        // {elem, nextLevel}
        var queue = [];
        var currentLevel = 0;
        var levelMap = {};
        
        queue.push({
            elem: root,
            level: currentLevel
        }); 
        
        while(queue.length){
            var currentItem = queue.shift();
         
            if(!levelMap[currentItem.level]){
                levelMap[currentItem.level] = [currentItem.elem.val]
            } else {
                levelMap[currentItem.level].push(currentItem.elem.val)
            }
            
            if(currentItem.elem.left){
                queue.push({
                    elem: currentItem.elem.left,
                    level: currentItem.level+1
                })
            }
            if(currentItem.elem.right){
                queue.push({
                    elem: currentItem.elem.right,
                    level: currentItem.level+1
                })
            }      
        }
        
        var result = [];
        for(var i = 0; i < Object.keys(levelMap).length; i++){
            result.push(levelMap[i]);
        }
        
        return result;
    };

Log in to reply
 

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