109. Convert Sorted List to Binary Search Tree - cocoder39/coco39_LC GitHub Wiki

109. Convert Sorted List to Binary Search Tree

solution 1: inorder traversal, t = O(n)

kind of like we have serialized a bst to linkedlist using in-order traversal, now we want to deserialize it.

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        size = self.getSize(head)
        self.head = head
        return self.helper(0, size-1)
    
    def helper(self, low, high):
        if low > high:
            return None

        mid = low + (high - low) // 2
        left = self.helper(low, mid-1)
        node = TreeNode(self.head.val)
        node.left = left
        self.head = self.head.next # moving head while traversing the list
        node.right = self.helper(mid+1, high)
        return node

    def getSize(self, head):
        cur = head
        size = 0
        while cur:
            size += 1
            cur = cur.next
        return size

solution 2: get mid, recursively build left subtree and right subtree, then combine them

t(n) = 2t(n/2) + n = O(n * log n)

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        
        if not head.next:
            return TreeNode(head.val)

        mid = self.splitAndReturnHeadOfSecondHalf(head)
        node = TreeNode(mid.val)
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(mid.next)
        return node

    # head has at least 2 nodes
    def splitAndReturnHeadOfSecondHalf(self, head) -> TreeNode:
        pre_slow = None
        slow = head
        fast = head
        # 1->2: return 2
        # 1->2->3: return 2
        # 1->2->3->4: return 3
        while fast and fast.next: 
            pre_slow = slow
            slow = slow.next
            fast = fast.next.next
        
        headOfSecondHalf = slow
        pre_slow.next = None
        return headOfSecondHalf

method 1: t(n) = 2t(n/2) + n = O(n * log n) (same as merge sort), space is O(height)

TreeNode* sortedListToBST(ListNode* head) {
        if (! head) {
            return nullptr;
        } else if (! head->next) {
            return new TreeNode(head->val);
        }
        
        //if 1+2n, fast stops at 1+2n and slow stops at 1+n, root is n+1
        //if 1+2n+1, fast stops at 1+2n+2(nullptr) and slow stps at 1+n+1, root is n+1/n+2
        ListNode *slow = head, *fast = head, *preSlow = nullptr;
        while (fast && fast->next) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        
        preSlow->next = nullptr; // preSlow != nullptr => at least 2 nodes
        TreeNode* root = new TreeNode(slow->val); // slow != nullptr => at least 1 node
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(slow->next); // slow != nullptr => at least 1 node
        return root;
    }

method 2: alike inorder traversal, traversal linked list and link treenode one by one. a bottom-up way of building bst.

tip : to ensure head points to mid between start and end when creating root, we pass ListNode* &head to helper(), rather than ListNode* head.

TreeNode* left = helper(head, start, mid - 1);
TreeNode* root = new TreeNode(head->val);

time is O(n) since each node would only be visited once, space is O(height)

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int sz = 0;
        ListNode* cur = head;
        while (cur) {
            cur = cur->next;
            sz++;
        }
        
        cur = head;
        return helper(cur, 0, sz - 1);
    }
private:
    TreeNode* helper(ListNode* &head, int start, int end) {
        if (start > end) {
            return nullptr;
        }
        
        int mid = start + (end - start) / 2;
        TreeNode* left = helper(head, start, mid - 1);
        TreeNode* root = new TreeNode(head->val);
        root->left = left;
        head = head->next;
        root->right = helper(head, mid + 1, end);
        return root;
    }
};