In this Leetcode Convert Sorted Array to Binary Search Tree problem solution we have Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
Problem solution in Python.
class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: n = len(nums) if n == 0: return None return self.arr2bst_helper(nums, 0, n-1, n) def arr2bst_helper(self, nums, lo, hi, n): if lo > hi: return None mid = (lo+hi)//2 node = TreeNode(nums[mid]) if lo == hi: return node node.left = self.arr2bst_helper(nums, lo, mid-1, n) node.right = self.arr2bst_helper(nums, mid+1, hi, n) return node
Problem solution in Java.
public TreeNode sortedArrayToBST(int[] nums) { TreeNode root=arrToTree(nums,0,nums.length-1); return root; } public TreeNode arrToTree(int[] nums, int start, int end){ if(start>end) return null; if(start==end) return new TreeNode(nums[start]); int mid= (end-start+1)/2 +start; TreeNode Mid= new TreeNode(nums[mid]); Mid.left= arrToTree(nums,start,mid-1); Mid.right=arrToTree(nums,mid+1,end); return Mid; }
Problem solution in C++.
class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { if (nums.empty()) { return nullptr; } auto p_root_node = new(TreeNode*); helper(p_root_node, nums, 0, nums.size()-1); return *p_root_node; } void helper(TreeNode** node, vector<int>& nums, int left_bound, int right_bound) { if (left_bound > right_bound) { return; } int mid = (left_bound+right_bound)/2; *node = new TreeNode(nums[mid]); helper(&(*node)->left, nums, left_bound, mid-1); helper(&(*node)->right, nums, mid+1, right_bound); } };
Problem solution in C.
void createTree(struct TreeNode *node, int *arr, int lindex, int rindex) { struct TreeNode *lnode, *rnode; int mid = (lindex + rindex) / 2 ; node->val = arr[mid]; if (lindex < mid) { lnode = calloc(1, sizeof(struct TreeNode)); node->left = lnode; createTree(lnode, arr, lindex, mid-1); } if (rindex > mid) { rnode = calloc(1, sizeof(struct TreeNode)); node->right = rnode; createTree(rnode, arr, mid+1, rindex); } } struct TreeNode* sortedArrayToBST(int* nums, int numsSize){ struct TreeNode *node = NULL; if (numsSize > 0) { node = calloc(1, sizeof(struct TreeNode)); createTree(node, nums, 0, numsSize-1); } return node; }