Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balancedbinary search tree.
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,null,3] and [3,1] are both height-balanced BSTs.
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.
Solutions
Solution 1: Binary Search + Recursion
We design a recursive function $dfs(l, r)$, which indicates that the node values of the current binary search tree to be constructed are all within the index range $[l, r]$ of the array nums. This function returns the root node of the constructed binary search tree.
The execution process of the function $dfs(l, r)$ is as follows:
If $l > r$, it means the current array is empty, return null.
If $l \leq r$, take the element with the index $mid = \lfloor \frac{l + r}{2} \rfloor$ in the array as the root node of the current binary search tree, where $\lfloor x \rfloor$ represents rounding down $x$.
Recursively construct the left subtree of the current binary search tree, whose root node value is the element with the index $mid - 1$ in the array, and the node values of the left subtree are all within the index range $[l, mid - 1]$ of the array.
Recursively construct the right subtree of the current binary search tree, whose root node value is the element with the index $mid + 1$ in the array, and the node values of the right subtree are all within the index range $[mid + 1, r]$ of the array.
Return the root node of the current binary search tree.
The answer is the return value of the function $dfs(0, n - 1)$.
The time complexity is $O(n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array nums.
1 2 3 4 5 6 7 8 91011121314151617
# 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 = rightclassSolution:defsortedArrayToBST(self,nums:List[int])->Optional[TreeNode]:defdfs(l,r):ifl>r:returnNonemid=(l+r)>>1left=dfs(l,mid-1)right=dfs(mid+1,r)returnTreeNode(nums[mid],left,right)returndfs(0,len(nums)-1)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcsortedArrayToBST(nums[]int)*TreeNode{vardfsfunc(int,int)*TreeNodedfs=func(l,rint)*TreeNode{ifl>r{returnnil}mid:=(l+r)>>1left,right:=dfs(l,mid-1),dfs(mid+1,r)return&TreeNode{nums[mid],left,right}}returndfs(0,len(nums)-1)}