C++, O(n)-time, Short Code


  • 0
    TreeNode* sortedListToBST(ListNode* head) {
        int len = 0;
        for (auto p = head; p; p = p->next, len++);
        return helper(head, len);
    }
    TreeNode* helper(ListNode *& node, int len) {
        if (len == 0) return NULL;
        auto left = helper(node, len/2);
        auto root = new TreeNode(node->val);
        root->left = left;
        node = node->next;
        root->right = helper(node, len - len/2 - 1);
        return root;
    }
    

Log in to reply
 

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