108. Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5
Rust Solution
struct Solution;
use rustgym_util::*;
impl Solution {
fn sorted_array_to_bst(nums: Vec<i32>) -> TreeLink {
let n = nums.len();
match n {
0 => None,
1 => tree!(nums[0]),
_ => {
let mid = n / 2;
let left = nums[..mid].to_vec();
let right = nums[mid + 1..].to_vec();
tree!(
nums[mid],
Self::sorted_array_to_bst(left),
Self::sorted_array_to_bst(right)
)
}
}
}
}
#[test]
fn test() {
let nums = vec![-10, -3, 0, 5, 9];
let bst = tree!(0, tree!(-3, tree!(-10), None), tree!(9, tree!(5), None));
assert_eq!(Solution::sorted_array_to_bst(nums), bst);
}
Having problems with this solution? Click here to submit an issue on github.