-
Notifications
You must be signed in to change notification settings - Fork 0
109_ConvertSortedListtoBinarySearchTree
a920604a edited this page Apr 14, 2023
·
1 revision
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if(!head) return nullptr;
if(!head->next) return new TreeNode(head->val);
ListNode *slow = head, *fast = head, *pre = head;
while(fast && fast->next){
pre = slow;
fast =fast->next->next;
slow = slow->next;
}
pre->next = nullptr;
TreeNode *root = new TreeNode(slow->val);
root->left = sortedListToBST(head);
if(slow->next) root->right = sortedListToBST(slow->next);
return root;
}
};
- time complexity
O(n)
- space complexity
O(n)
footer