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


  • 0
    X

    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 {
    public:
        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)
        		sum++;
        	return sum;
        }
    };
    

Log in to reply
 

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