108. Convert Sorted Array to Binary Search Tree Easy

1/**
2 * [108] Convert Sorted Array to Binary Search Tree
3 *
4 * Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
5 * A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/btree1.jpg" style="width: 302px; height: 222px;" />
9 * Input: nums = [-10,-3,0,5,9]
10 * Output: [0,-3,9,-10,null,5]
11 * Explanation: [0,-10,5,null,-3,null,9] is also accepted:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/btree2.jpg" style="width: 302px; height: 222px;" />
13 * 
14 * Example 2:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/18/btree.jpg" style="width: 342px; height: 142px;" />
16 * Input: nums = [1,3]
17 * Output: [3,1]
18 * Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
19 * 
20 *  
21 * Constraints:
22 * 
23 * 	1 <= nums.length <= 10^4
24 * 	-10^4 <= nums[i] <= 10^4
25 * 	nums is sorted in a strictly increasing order.
26 * 
27 */
28pub struct Solution {}
29use crate::util::tree::{TreeNode, to_tree};
30
31// problem: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
32// discuss: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/?currentPage=1&orderBy=most_votes&query=
33
34// submission codes start here
35
36// Definition for a binary tree node.
37// #[derive(Debug, PartialEq, Eq)]
38// pub struct TreeNode {
39//   pub val: i32,
40//   pub left: Option<Rc<RefCell<TreeNode>>>,
41//   pub right: Option<Rc<RefCell<TreeNode>>>,
42// }
43// 
44// impl TreeNode {
45//   #[inline]
46//   pub fn new(val: i32) -> Self {
47//     TreeNode {
48//       val,
49//       left: None,
50//       right: None
51//     }
52//   }
53// }
54use std::rc::Rc;
55use std::cell::RefCell;
56impl Solution {
57    pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
58        Some(Rc::new(RefCell::new(TreeNode::new(0))))
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_108() {
70    }
71}
72