Easy JavaScript solution using BFS, no map, beats 95%


  • 0
    var verticalOrder = function(root) {
        if (!root) return [];
        
        root.offset = 0;
        const queue = [root];
        
        const res = [];
        let rootLevel = 0;
        
        while (queue.length) {
            let node = queue.shift();
            
            if (res[rootLevel + node.offset]) {
                res[rootLevel + node.offset].push(node.val);
            } else if (node.offset < 0) {
                res.unshift([node.val]);
                rootLevel++;
            } else {
                res.push([node.val]);
            }
            
            if (node.left) {
                node.left.offset = node.offset - 1;
                queue.push(node.left);
            }
            if (node.right) {
                node.right.offset = node.offset + 1;
                queue.push(node.right);
            }
        }
        
        return res;
    };
    
    1. Track the vertical level of the root node.
    2. Store the vertical level offset from the root node inside each queued node.
    3. If the vertical level corresponding to a visiting node doesn't exist on the left, we shift our results to the right and increment the root vertical level; for the right side we simply push on a new level.

Log in to reply
 

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