109. Convert Sorted List to Binary Search Tree Medium

1/**
2 * [109] Convert Sorted List to Binary Search Tree
3 *
4 * Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
5 * 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/08/17/linked.jpg" style="width: 500px; height: 388px;" />
9 * Input: head = [-10,-3,0,5,9]
10 * Output: [0,-3,9,-10,null,5]
11 * Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
12 * 
13 * Example 2:
14 * 
15 * Input: head = []
16 * Output: []
17 * 
18 *  
19 * Constraints:
20 * 
21 * 	The number of nodes in head is in the range [0, 2 * 10^4].
22 * 	-10^5 <= Node.val <= 10^5
23 * 
24 */
25pub struct Solution {}
26use crate::util::linked_list::{ListNode, to_list};
27use crate::util::tree::{TreeNode, to_tree};
28
29// problem: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
30// discuss: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/?currentPage=1&orderBy=most_votes&query=
31
32// submission codes start here
33
34// Definition for singly-linked list.
35// #[derive(PartialEq, Eq, Clone, Debug)]
36// pub struct ListNode {
37//   pub val: i32,
38//   pub next: Option<Box<ListNode>>
39// }
40// 
41// impl ListNode {
42//   #[inline]
43//   fn new(val: i32) -> Self {
44//     ListNode {
45//       next: None,
46//       val
47//     }
48//   }
49// }
50// Definition for a binary tree node.
51// #[derive(Debug, PartialEq, Eq)]
52// pub struct TreeNode {
53//   pub val: i32,
54//   pub left: Option<Rc<RefCell<TreeNode>>>,
55//   pub right: Option<Rc<RefCell<TreeNode>>>,
56// }
57// 
58// impl TreeNode {
59//   #[inline]
60//   pub fn new(val: i32) -> Self {
61//     TreeNode {
62//       val,
63//       left: None,
64//       right: None
65//     }
66//   }
67// }
68use std::rc::Rc;
69use std::cell::RefCell;
70impl Solution {
71    pub fn sorted_list_to_bst(head: Option<Box<ListNode>>) -> Option<Rc<RefCell<TreeNode>>> {
72        Some(Rc::new(RefCell::new(TreeNode::new(0))))
73    }
74}
75
76// submission codes end
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    #[test]
83    fn test_109() {
84    }
85}
86