solve #108

aylei · aylei · commit aa7003433baf · 2019-02-13T11:26:54.000+08:00
diff --git a/src/lib.rs b/src/lib.rs
@@ -108,3 +108,4 @@ mod n0104_maximum_depth_of_binary_tree;
 mod n0105_construct_binary_tree_from_preorder_and_inorder_traversal;
 mod n0106_construct_binary_tree_from_inorder_and_postorder_traversal;
 mod n0107_binary_tree_level_order_traversal_ii;
+mod n0108_convert_sorted_array_to_binary_search_tree;
diff --git a/src/n0108_convert_sorted_array_to_binary_search_tree.rs b/src/n0108_convert_sorted_array_to_binary_search_tree.rs
@@ -0,0 +1,56 @@
+/**
+ * [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
+ * 
+ * 
+ */
+pub struct Solution {}
+use super::util::tree::{TreeNode, to_tree};
+
+// submission codes start here
+
+use std::rc::Rc;
+use std::cell::RefCell;
+impl Solution {
+    pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
+        Solution::bst_helper(&nums[..])
+    }
+
+    fn bst_helper(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
+        if nums.is_empty() { return None }
+        Some(Rc::new(RefCell::new(TreeNode{
+            val: nums[nums.len() / 2],
+            left: Solution::bst_helper(&nums[0..(nums.len()/2)]),
+            right: Solution::bst_helper(&nums[(nums.len()/2+1)..]),
+        })))
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_108() {
+        assert_eq!(Solution::sorted_array_to_bst(vec![-10,-3,0,5,9]), tree![0,-3,9,-10,null,5]);
+        assert_eq!(Solution::sorted_array_to_bst(vec![]), tree![]);
+    }
+}
