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[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);
}