Description Link to heading

109. Convert Sorted List to Binary Search Tree (Medium)

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balancedbinary 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⁴].
  • -10⁵ <= Node.val <= 10⁵

Solution Link to heading

Initially, if we substitute a linked list with an array, it becomes quite convenient to accomplish the task within a temporal complexity of $O(n)$. Subsequently, since a linked list cannot facilitate random access in $O(1)$ time akin to an array, it is not amenable to an array-centric approach.

Primarily, we must contemplate that performing an in-order traversal on a binary search tree yields an ascending order list. Therefore, we can also derive a binary search tree through a process akin to an in-order traversal. That is to say, first, calculate the left child node, the root node being the current node under traversal, followed by the computation of the right child node.

Code Link to heading 

class Solution {
  public:
    TreeNode *dfs(int l, int r, ListNode **head) {
        if (l >= r) {
            return nullptr;
        }
        int mid = l + (r - l) / 2;
        TreeNode *left = dfs(l, mid, head);
        TreeNode *root = new TreeNode((*head)->val);
        root->left = left;
        *head = (*head)->next;
        root->right = dfs(mid + 1, r, head);
        return root;
    }
    TreeNode *sortedListToBST(ListNode *head) {
        ListNode *tail = head;
        int cnt = 0;
        while (tail != nullptr) {
            ++cnt;
            tail = tail->next;
        }
        return dfs(0, cnt, &head);
    }
};