Algorithm
Problem Nmae: 108. Convert Sorted Array to Binary Search Tree
problem Link: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
binary search tree.
Given an integer array nums where the elements are sorted in ascending order, convert it to a
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 <= 104-104 <= nums[i] <= 104numsis sorted in a strictly increasing order.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct TreeNode *gen_tree(int *nums, int start, int end) {
struct TreeNode *node;
int mid;
if (start > end) return NULL;
node = malloc(sizeof(struct TreeNode));
//assert(node);
mid = start + (end - start) / 2;
node->val = nums[mid];
node->left = gen_tree(nums, start, mid - 1); // sub tree on left
node->right = gen_tree(nums, mid + 1, end); // sub tree on right
return node;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
return gen_tree(nums, 0, numsSize - 1);
}
Input
nums = [-10,-3,0,5,9]
Output
[0,-3,9,-10,null,5]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.empty()) return NULL;
TreeNode* root = new TreeNode(nums[nums.size() / 2]);
vector<int>left(nums.begin(), nums.begin() + nums.size() / 2);
vector<int>right(nums.begin() + nums.size() / 2 + 1, nums.end());
root->left = sortedArrayToBST(left);
root->right = sortedArrayToBST(right);
return root;
}
};
Input
nums = [-10,-3,0,5,9]
Output
[0,-3,9,-10,null,5]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
private TreeNode helper(int[] nums, int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, start, mid - 1);
root.right = helper(nums, mid + 1, end);
return root;
}
}
Input
nums = [1,3]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const sortedArrayToBST = function(nums) {
if (nums.length == 0) {
return null;
}
const head = helper(nums, 0, nums.length - 1);
return head;
};
function helper(num, low, high) {
if (low > high) {
// Done
return null;
}
let mid = Math.floor((low + high) / 2);
let node = new TreeNode(num[mid]);
node.left = helper(num, low, mid - 1);
node.right = helper(num, mid + 1, high);
return node;
}
Input
nums = [1,3]
Output
[3,1]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if nums==[]:
return
root=TreeNode(nums[len(nums)//2])
root.left=self.sortedArrayToBST(nums[:len(nums)//2])
root.right=self.sortedArrayToBST(nums[len(nums)//2+1:])
return root
Input
nums = [-10,-3,0,5,9]
Output
[0,-3,9,-10,null,5]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _108_ConvertSortedArrayToBinarySearchTree
{
public TreeNode SortedArrayToBST(int[] nums)
{
return SortedArraryToBST(nums, 0, nums.Length);
}
private TreeNode SortedArraryToBST(int[] nums, int l, int r)
{
if (l >= r) return null;
var mid = (r - l) / 2 + l;
var node = new TreeNode(nums[mid]);
node.left = SortedArraryToBST(nums, l, mid);
node.right = SortedArraryToBST(nums, mid + 1, r);
return node;
}
}
}
Input
nums = [-10,-3,0,5,9]
Output
[0,-3,9,-10,null,5]