Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 11

Description

Convert Sorted List to Binary Search Tree

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

Example 2:

Input: head = []
Output: []

Constraints:

• The number of nodes in head is in the range [0, 2 * 104].
• -105 <= Node.val <= 105

Solution

class Solution {
  ListNode *cur;
  
  int length(ListNode *head) {
    int len = 0;
    while(head) {
      len += 1;
      head = head->next;
    }
    return len;
  }
  
  TreeNode *buildBST(int begin, int end) {
    if(begin > end) return nullptr;
    
    int mid = (begin + end) >> 1;
    TreeNode *left = buildBST(begin, mid - 1);
    
    TreeNode *root = new TreeNode(cur->val);
    root->left = left;
    
    cur = cur->next;
    root->right = buildBST(mid + 1, end);
    
    return root;
  }
  
public:
  TreeNode* sortedListToBST(ListNode* head) {
    int len = length(head);
    cur = head;
    return buildBST(0, len-1);
  }
};

// Accepted
// 32/32 cases passed (24 ms)
// Your runtime beats 84.58 % of cpp submissions
// Your memory usage beats 71.93 % of cpp submissions (28.4 MB)