Description:
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Examples:
Example 1:
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Example 2:
Input: nums = [1,3]
Output: [3,1]Solution in Python:
To convert a sorted integer array into a height-balanced binary search tree (BST), we can use a recursive approach. A height-balanced BST ensures that the depth of the two subtrees of every node never differs by more than one.
Here’s a step-by-step approach to solve this problem:
- Identify the Middle Element: The middle element of the sorted array will be the root of the BST. This ensures that the tree is balanced because the number of nodes in the left subtree and the right subtree will be as equal as possible.
- Recursive Division: The elements to the left of the middle element will form the left subtree, and the elements to the right will form the right subtree. We will recursively apply this step to form the left and right subtrees.
- Base Case: When the subarray has no elements, return
None(this will be the leaf node’s children).
Python
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedArrayToBST(self, nums):
"""
Convert sorted array to height-balanced BST.
:type nums: List[int]
:rtype: TreeNode
"""
# Helper function to construct BST from subarray
def helper(left, right):
if left > right:
return None
# Always choose the middle element to ensure balance
mid = (left + right) // 2
node = TreeNode(nums[mid])
# Recursively build the left and right subtrees
node.left = helper(left, mid - 1)
node.right = helper(mid + 1, right)
return node
return helper(0, len(nums) - 1)
# Example usage:
# solution = Solution()
# tree = solution.sortedArrayToBST([-10, -3, 0, 5, 9])Explanation:
- TreeNode Class:
- This class defines the structure of each node in the binary search tree.
- sortedArrayToBST Method:
- This method initializes the recursive process to convert the sorted array into a BST.
- helper Function:
- Base Case: When
leftindex exceedsrightindex, returnNone. This marks the end of a branch in the tree. - Middle Element: Calculate the middle index of the current subarray and create a
TreeNodewith this value. - Recursive Calls: Recursively build the left subtree using elements before the middle and the right subtree using elements after the middle.
- Return: Return the constructed node, which becomes part of the BST.
- Base Case: When
Usage Example:
- An instance of the
Solutionclass is created. - The
sortedArrayToBSTmethod is called with a sorted array, returning the root of the height-balanced BST.
Solution in Javascript:
JavaScript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
/**
* Helper function to build the BST from a subarray
* @param {number} left - Left index of the current subarray
* @param {number} right - Right index of the current subarray
* @return {TreeNode} - Root node of the constructed BST
*/
const helper = function(left, right) {
// Base case: If the left index exceeds the right index, return null
if (left > right) {
return null;
}
// Middle element to maintain balance
const mid = Math.floor((left + right) / 2);
// Create a new TreeNode with the middle element
const node = new TreeNode(nums[mid]);
// Recursively build the left and right subtrees
node.left = helper(left, mid - 1);
node.right = helper(mid + 1, right);
// Return the constructed node
return node;
};
// Start the recursion with the full range of the input array
return helper(0, nums.length - 1);
};
// Example usage:
const nums = [-10, -3, 0, 5, 9];
const tree = sortedArrayToBST(nums);
console.log(tree);Solution in Java:
Java
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
/**
* Helper function to construct BST from subarray
* @param nums - The entire array
* @param left - Left index of the current subarray
* @param right - Right index of the current subarray
* @return TreeNode - Root node of the constructed BST
*/
private TreeNode helper(int[] nums, int left, int right) {
// Base case: If left index exceeds right index, return null
if (left > right) {
return null;
}
// Middle element to ensure balance
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
// Recursively build the left and right subtrees
node.left = helper(nums, left, mid - 1);
node.right = helper(nums, mid + 1, right);
// Return the constructed node
return node;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-10, -3, 0, 5, 9};
TreeNode root = solution.sortedArrayToBST(nums);
// Printing the tree (in-order traversal) to verify the result
printTree(root);
}
// Helper function to print the tree (in-order traversal)
private static void printTree(TreeNode node) {
if (node != null) {
printTree(node.left);
System.out.print(node.val + " ");
printTree(node.right);
}
}
}Solution in C#:
C#
public class Solution {
public TreeNode SortedArrayToBST(int[] nums) {
return Helper(nums, 0, nums.Length - 1);
}
private TreeNode Helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = Helper(nums, left, mid - 1);
node.right = Helper(nums, mid + 1, right);
return node;
}
}