Easy-to-understand O(n) solution adapted from the official leetcode solution

  • 0

    I never fully understand why the solution people refer to is indeed working. So I change it slightly with my own understanding. Hopefully it is easier for you to grasp, too.

    class Solution {
        TreeNode *sortedListToBST(ListNode *head) {
            int n = length(head);
            return sortedListToBSTHelper(head, n);
        // create a balanced BST using @len elements starting from @head & move @head forward by @len
        TreeNode *sortedListToBSTHelper(ListNode *&head, int len) {
        	if (0 == len)	return NULL;
        	auto left = sortedListToBSTHelper(head, len / 2);
        	auto root = new TreeNode(head->val);
        	root->left = left;
        	head = head->next;
        	root->right = sortedListToBSTHelper(head, (len - 1) / 2);
        	return root;
        int length(ListNode *head) {
        	int sum = 0;
        	for (auto p = head; p; p = p->next)
        	return sum;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.