Sponsored
Sponsored
This approach selects the middle element of the current array (or subarray) to ensure a balanced partitioning of elements, thus maintaining the height balance of the BST.
The middle element of the array becomes the root of the BST (or subtree), and the same operation is recursively applied to the left and right halves of the array to form the left and right subtrees respectively.
Time Complexity: O(n), where n is the number of elements in the array, because each element is visited once.
Space Complexity: O(log n) due to the recursion stack in a balanced tree scenario.
1public class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode sortedArrayToBST(int[] nums) {
10 return sortedArrayToBSTHelper(nums, 0, nums.length - 1);
11 }
12
13 private TreeNode sortedArrayToBSTHelper(int[] nums, int left, int right) {
14 if (left > right) {
15 return null;
16 }
17 int mid = left + (right - left) / 2;
18 TreeNode node = new TreeNode(nums[mid]);
19 node.left = sortedArrayToBSTHelper(nums, left, mid - 1);
20 node.right = sortedArrayToBSTHelper(nums, mid + 1, right);
21 return node;
22 }
23}In this Java implementation, the recursive strategy is similarly employed to break down the array and form a balanced BST by establishing midpoints as roots for subtrees.