109.Convert Sorted List to Binary Search Tree

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

109. 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⁴].
• -10⁵ <= Node.val <= 10⁵

解答

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);
    }
};

Yen-Chi ChenSun, 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)

Yen-Chi ChenSun, Mar 12, 2023

Reference

回到題目列表