109

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

Example 3:

Input: head = [0]
Output: [0]

Example 4:

Input: head = [1,3]
Output: [3,1]

 

Constraints:

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

Companies:
Facebook, Microsoft, Oracle

Related Topics:
Linked List, Depth-first Search

Similar Questions:

• Convert Sorted Array to Binary Search Tree (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(logN)
class Solution {
    int getLength(ListNode *head) {
        int ans = 0;
        for (; head; head = head->next, ++ans);
        return ans;
    }
    TreeNode *dfs(ListNode *head, int len) {
        if (len == 0) return NULL;
        if (len == 1) return new TreeNode(head->val);
        auto p = head;
        for (int i = 0; i < len / 2; ++i) p = p->next;
        auto root = new TreeNode(p->val);
        root->left = dfs(head, len / 2);
        root->right = dfs(p->next, (len - 1) / 2);
        return root;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int len = getLength(head);
        return dfs(head, len);
    }
};

Solution 2. Fast Slow Pointers

// OJ: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(logN)
class Solution {
    TreeNode *dfs(ListNode *head, ListNode *end) {
        if (head == end) return NULL;
        if (head->next == end) return new TreeNode(head->val);
        auto p = head, q = head;
        while (q != end && q->next != end) {
            p = p->next;
            q = q->next->next;
        }
        auto root = new TreeNode(p->val);
        root->left = dfs(head, p);
        root->right = dfs(p->next, end);
        return root;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return dfs(head, NULL);
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
class Solution {
    ListNode *head;
    int getLength(ListNode *head) {
        int ans = 0;
        for (; head; head = head->next, ++ans);
        return ans;
    }
    TreeNode *dfs(int begin, int end) {
        if (begin == end) return NULL;
        int mid = (begin + end) / 2;
        auto left = dfs(begin, mid);
        auto root = new TreeNode(head->val);
        head = head->next;
        root->left = left;
        root->right = dfs(mid + 1, end);
        return root;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        this->head = head;
        return dfs(0, getLength(head));
    }
};