Convert Sorted Array to Binary Search Tree 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.
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,3] and [3,1] are both a height-balanced BSTs.
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
private:
TreeNode* build(const vector<int>& nums, int l, int r) {
if (l > r)
return nullptr;
const int m = l + (r - l) / 2;
return new TreeNode(nums[m],
build(nums, l, m - 1),
build(nums, m + 1, r));
}
};
Java
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int l, int r) {
if (l > r)
return null;
final int m = l + (r - l) / 2;
return new TreeNode(nums[m],
build(nums, l, m - 1),
build(nums, m + 1, r));
}
}
Python
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def build(l: int, r: int) -> Optional[TreeNode]:
if l > r:
return None
m = (l + r) // 2
return TreeNode(nums[m],
build(l, m - 1),
build(m + 1, r))
return build(0, len(nums) - 1)