Description
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary 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] <= 104nums is sorted in a strictly increasing order.
Solutions
Solution 1: Binary Search + Recursion
We design a recursive function dfs(l, r), which represents that the values of the nodes to be constructed in the current binary search tree are 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, so return
null.
- If l ≤ r, take the element at index mid = \lfloor l + r⁄2 \rfloor of the array as the root node of the current binary search tree, where \lfloor x \rfloor denotes the floor function of x.
- Recursively construct the left subtree of the current binary search tree, with the root node's value being the element at index mid - 1 of the array. The values of the nodes in the left subtree are within the index range [l, mid - 1] of the array.
- Recursively construct the right subtree of the current binary search tree, with the root node's value being the element at index mid + 1 of the array. The values of the nodes in the right subtree are 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.
PythonJavaC++GoTypeScriptRustJavaScriptC#
# 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: List[int]) -> Optional[TreeNode]:
def dfs(l: int, r: int) -> Optional[TreeNode]:
if l > r:
return None
mid = (l + r) >> 1
return TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r))
return dfs(0, len(nums) - 1)(code-box)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int[] nums;
public TreeNode sortedArrayToBST(int[] nums) {
this.nums = nums;
return dfs(0, nums.length - 1);
}
private TreeNode dfs(int l, int r) {
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return new TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r));
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
auto dfs = [&](this auto&& dfs, int l, int r) -> TreeNode* {
if (l > r) {
return nullptr;
}
int mid = (l + r) >> 1;
return new TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r));
};
return dfs(0, nums.size() - 1);
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
var dfs func(int, int) *TreeNode
dfs = func(l, r int) *TreeNode {
if l > r {
return nil
}
mid := (l + r) >> 1
return &TreeNode{nums[mid], dfs(l, mid-1), dfs(mid+1, r)}
}
return dfs(0, len(nums)-1)
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function sortedArrayToBST(nums: number[]): TreeNode | null {
const dfs = (l: number, r: number): TreeNode | null => {
if (l > r) {
return null;
}
const mid = (l + r) >> 1;
return new TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r));
};
return dfs(0, nums.length - 1);
}(code-box)
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
fn dfs(nums: &Vec<i32>, l: usize, r: usize) -> Option<Rc<RefCell<TreeNode>>> {
if l > r {
return None;
}
let mid = (l + r) / 2;
if mid >= nums.len() {
return None;
}
let mut node = Rc::new(RefCell::new(TreeNode::new(nums[mid])));
node.borrow_mut().left = dfs(nums, l, mid - 1);
node.borrow_mut().right = dfs(nums, mid + 1, r);
Some(node)
}
dfs(&nums, 0, nums.len() - 1)
}
}(code-box)
/**
* 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) {
const dfs = (l, r) => {
if (l > r) {
return null;
}
const mid = (l + r) >> 1;
return new TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r));
};
return dfs(0, nums.length - 1);
};(code-box)
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
private int[] nums;
public TreeNode SortedArrayToBST(int[] nums) {
this.nums = nums;
return dfs(0, nums.Length - 1);
}
private TreeNode dfs(int l, int r) {
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
return new TreeNode(nums[mid], dfs(l, mid - 1), dfs(mid + 1, r));
}
}(code-box)
