Accepted two recursive solutions in Javascript. Why the latter is faster?


  • 0

    Many people already posted their solutions though but looks like i didn't see too many using Javascript, so I just share my codes as below:

    the first one to traverse the list first, and turn it into problem https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

    /**
     * Memo: Traverse the list and put nodes in an array, then turn it into problem of sortedArrayToBST
     * Complex: O(nlogn)
     * Runtime: 192ms
     * Tests: 32 test cases passed
     * Rank: S
     */
    var sortedListToBST = function(head) {
        var sortedArrayToBST = function(num) {
            function convert(start, end) {
                var root = null;
                if (start <= end) {
                    var mid = ~~((start + end) / 2);
                    if (typeof num[mid] !== 'undefined') {
                        root = new TreeNode(num[mid]);
                        root.left = convert(start, mid - 1);
                        root.right = convert(mid + 1, end);
                    }
                }
                return root;
            }
    
            return convert(0, num.length);
        };
    
    
        if (!head) return null;
    
        var nodes = [];
        var p = head;
        while (p) {
            nodes.push(p.val);
            p = p.next;
        }
    
        return sortedArrayToBST(nodes);
    };
    

    The second one use fast/slow pointer to find the new root element, them treat the elements before/after it recusively.

    /**
     * Memo: Use fast and slow pointers to find element mid, use it as root and break it into two lists (by using prev pointer), then solve it recusively.
     * Complex: O(nlogn)
     * Runtime: 164ms
     * Tests: 32 test cases passed
     * Rank: S
     */
    var sortedListToBST = function(head) {
        if (!head) return null;
        if (!head.next) return new TreeNode(head.val); //Need to return new TreeNode here
    
        var fast = head;
        var slow = head;
        var prev = head;
    
        while (fast) {
            fast = fast.next;
            if (fast) {
                prev = slow;
                slow = slow.next;
                fast = fast.next;
            }
        }
        prev.next = null; // break original list into two lists
        var root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    };
    

    At first I thought the first method would be faster, as the latter need to relocate the root again and again from head to tail, but on average the latter is faster. Anyone has any thoughts?


Log in to reply
 

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