LeetCode Solutions
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (head == nullptr)
return nullptr;
if (!head->next)
return new TreeNode(head->val);
ListNode* mid = findMid(head);
TreeNode* root = new TreeNode(mid->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(mid->next);
return root;
}
private:
ListNode* findMid(ListNode* head) {
ListNode* prev = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;
return slow;
}
};
|
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
if (head.next == null)
return new TreeNode(head.val);
ListNode mid = findMid(head);
TreeNode root = new TreeNode(mid.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
private ListNode findMid(ListNode head) {
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
return slow;
}
}
|
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
def findMid(head: ListNode) -> ListNode:
prev = None
slow = head
fast = head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
return slow
if not head:
return None
if not head.next:
return TreeNode(head.val)
mid = findMid(head)
root = TreeNode(mid.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(mid.next)
return root
|
