DFS inorder without calculating the middle node beats 80%


  • 0
    L

    The solution is to add a range when using DFS, [left, right], so that we can use the range to exit the recursion.

    Also, note the reference usage in the convert function ListNode* &h, otherwise the outside recursion cannot get the correct value.

    
      TreeNode* sortedListToBST(ListNode* head) {
        auto n = count(head);
        return convert(head, 0, n - 1);
      }
    
      int count(ListNode* h)
      {
        int cnt = 0;
        while (h != nullptr)
        {
          h = h->next;
          cnt++;
        }
        return cnt;
      }
    
      TreeNode* convert(ListNode* &h, int l, int r)
      {
    
        if (l > r) return nullptr;
    
    
        int m = l + (r - l) / 2;
    
        auto left = convert(h, l, m - 1);
        TreeNode * node = new TreeNode(h->val);
        h = h->next;
        auto right = convert(h, m + 1, r);
    
        node->left = left;
        node->right = right;
        return node;
      }
    

Log in to reply
 

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