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
```

108. Convert Sorted Array to Binary Search Tree
``````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),
_ => {
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);
}
``````