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 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode SortedArrayToBST(int[] nums) {
10 return SortedArrayToBST(nums, 0, nums.Length - 1);
11 }
12
13 private TreeNode SortedArrayToBST(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 = SortedArrayToBST(nums, left, mid - 1);
20 node.right = SortedArrayToBST(nums, mid + 1, right);
21 return node;
22 }
23}This C# solution mirrors the recursive approach to efficiently form subtrees, ensuring each element finds its place in the height-balanced BST.