109.Convert Sorted List to Binary Search Tree
===

###### tags: `Medium`,`Linked List`,`Tree`,`Divide and Conquer`

[109. Convert Sorted List to Binary Search Tree](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 binary search tree*.

### 範例

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

**Constraints**:

* The number of nodes in `head` is in the range [0, 2 * 10^4^].
* -10^5^ <= `Node.val` <= 10^5^

### 解答
#### C++

class Solution {
public:
    TreeNode* dfs(ListNode* head, ListNode* tail) {
        if (head == tail) return nullptr;
        auto fast = head, slow = head;
        while (fast != tail && fast->next != tail) {
            fast = fast->next->next;
            slow = slow->next;
        }
        auto root = new TreeNode(slow->val, dfs(head, slow), dfs(slow->next, tail));
        return root;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return new TreeNode(head->val);
        return dfs(head, nullptr);
    }
};

> [name=Yen-Chi Chen][time=Sun, Mar 12, 2023]

#### Python

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        def dfs(head, tail):
            if head == tail: return None
            fast = slow = head
            while fast != tail and fast.next != tail:
                fast = fast.next.next
                slow = slow.next
            return TreeNode(slow.val, dfs(head, slow), dfs(slow.next, tail))
        
        if not head: return None
        if not head.next: return TreeNode(head.val);
        return dfs(head, None)

> [name=Yen-Chi Chen][time=Sun, Mar 12, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)