LeetCode //C - 108. Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height balanced binary search tree.
 

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

• 1 <= nums.length <= $10^4$
• -$10^4<=nums[i]<=10^4$
• nums is sorted in a strictly increasing order.

From: LeetCode
Link: 108. Convert Sorted Array to Binary Search Tree

---

Solution:

Ideas：

1. The helper function is used to convert a subarray defined by the start and end indices into a subtree of the BST.
2. If start > end, it means the subarray is empty and we return NULL.
3. We calculate the middle index of the subarray and use the element at that index to create a new tree node.
4. The left and right children of this new node are recursively determined by the left and right halves of the subarray.
5. The sortedArrayToBST function is just an entry point that calls the helper function using the entire array as the initial subarray.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* helper(int* nums, int start, int end) {
    if (start > end) {
        return NULL;
    }
    
    int mid = start + (end - start) / 2;
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = nums[mid];
    node->left = helper(nums, start, mid - 1);
    node->right = helper(nums, mid + 1, end);
    
    return node;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    return helper(nums, 0, numsSize - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25