JavaScript solution using linked list


  • 0
    1
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    
    var ListNode = function (){
        this.prev = null;
        this.next = null;
        this.vals = [];
    }
    
    /**
     * @param {TreeNode} root
     * @return {number[][]}
     */
    var verticalOrder = function(root) {
        if (root === null) {
            return [];
        }
        
        var queue = [];
        var rootListNode = new ListNode();
        queue.push({
            treeNode: root,
            listNode: rootListNode
        });
        
        while (queue.length > 0) {
            var next = queue.shift();
            next.listNode.vals.push(next.treeNode.val);
            
            if (next.treeNode.left) {
                if (!next.listNode.prev) {
                    next.listNode.prev = new ListNode();
                    next.listNode.prev.next = next.listNode;
                }
                queue.push({
                    treeNode: next.treeNode.left,
                    listNode: next.listNode.prev
                });
            }
            if (next.treeNode.right) {
                if (!next.listNode.next) {
                    next.listNode.next = new ListNode();
                    next.listNode.next.prev = next.listNode;
                }
                queue.push({
                    treeNode: next.treeNode.right,
                    listNode: next.listNode.next
                });
            }
        }
        
        var firstListNode = rootListNode;
        while (firstListNode.prev) {
            firstListNode = firstListNode.prev;
        }
        
        var traversal = [];
        var currentListNode = firstListNode;
        while (currentListNode) {
            var verticalSlice = currentListNode.vals;
            traversal.push(verticalSlice);
            currentListNode = currentListNode.next;
        }
        return traversal;
    };
    

Log in to reply
 

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