109. Convert Sorted List to Binary Search Tree

Leetcode

https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

題目

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

解答

• 方法一

var sortedListToBST = function(head) {
    const getNode = (head) => {
        if (!head) return null;
        
        let prevSlow = null;
        let slow = head;
        let fast = head;
        
        while (fast?.next) {
            prevSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        };
        
        const node = new TreeNode(slow.val);
        if (prevSlow) prevSlow.next = null;
        
        if (head === slow) return node;
        
        node.left = getNode(head);
        node.right = getNode(slow.next);
        return node;
    };
    
    return getNode(head);
};

Runtime: 80 ms, faster than 92.71% of JavaScript online submissions for Convert Sorted List to Binary Search Tree.

Memory Usage: 47.2 MB, less than 88.15% of JavaScript online submissions for Convert Sorted List to Binary Search Tree.

Time Complexity: O(NlogN)

分拆一個長度為 N 的 linked list 花費時間為 N / 2 (找到 middle 的時間)，總共會分拆 logN 次，所以全部加起來會是 O(NlogN)

Space Complexity: O(logN)

O(N) for skewed tree，O(logN) for height balanced tree

• 方法二

先將 linked list 轉為一般的 array，再套用 108. 題的解法，如此的話 Time Complexity 可以改進到 O(N)，但 Space Complexity 會變為 O(N)

var sortedListToBST = function(head) {
    const arr = [];
    while (head) {
        arr.push(head.val);    
        head = head.next;
    }
    
    // 以下為 108. 題解法
    const getNode = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        
        const val = arr[mid];
        const node = new TreeNode(val);
        
        node.left = getNode(left, mid - 1);
        node.right = getNode(mid + 1, right);
        
        return node;
    }
    
    return getNode(0, arr.length - 1);
};

Runtime: 95 ms, faster than 71.25% of JavaScript online submissions for Convert Sorted List to Binary Search Tree.

Memory Usage: 48 MB, less than 42.81% of JavaScript online submissions for Convert Sorted List to Binary Search Tree.

Time Complexity: O(N)

Space Complexity: O(N)

• 方法三

利用 inorder 排序的特性 (左子樹 => 中 => 右子樹)，可以依序的建立由左至右，由小到大的排序

首先 linked list 的第一個最小值，會被置放在最左下角的子樹，然後依序往上到根節點，再依序往下的右子樹進行排序

var sortedListToBST = function(head) {
    const getSize = (head) => {
        let count = 0;
        let node = head;
        while (node) {
            node = node.next;
            count++;
        }
        return count;
    }
    
    const getNode = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        
        // 先取得左子樹
        const leftNode = getNode(left, mid - 1);
        
        // 中間節點，第一輪遍歷的時候會是最左下角的節點
        const node = new TreeNode(head.val);
        node.left = leftNode;
        
        head = head.next;
        
        // 最後長出右子樹
        node.right = getNode(mid + 1, right);
        
        return node;
    }
    
    
    const size = getSize(head);
    return getNode(0, size - 1);
};

Runtime: 123 ms, faster than 40.00% of JavaScript online submissions for Convert Sorted List to Binary Search Tree.

Memory Usage: 47.3 MB, less than 78.75% of JavaScript online submissions for Convert Sorted List to Binary Search Tree.

Time Complexity: O(N)

Space Complexity: O(log N) => the height of a height balanced BST is log N