# 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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/17/linked.jpg)

```
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: []
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

```
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`
