Share my O(n) time and O(1) space C++ code


  • 0
    F
    TreeNode* sortedListToBST(ListNode* head) {
      int size = 0;
      ListNode* p = head;
      while (p != NULL) {
        size ++;
        p = p->next;
      }
    
      return generate(size, &head);
    }
    // like in-order traverse
    TreeNode* generate(int n, ListNode** head) {
      if (n == 0) return NULL;
      TreeNode* curNode = new TreeNode(0); // 0 is placeholder
      curNode->left = generate(n/2, head);
      curNode->val = (*head)->val;
      (*head) = (*head)->next;
      curNode->right = generate(n - n/2 - 1, head);
    
      return curNode;
    }
    

Log in to reply
 

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