solve #94 and add binary-tree util

aylei · aylei · commit 33eb153ff94e · 2019-02-08T20:04:25.000+08:00
diff --git a/src/lib.rs b/src/lib.rs
@@ -91,3 +91,7 @@ mod n0087_scramble_string;
 mod n0088_merge_sorted_array;
 mod n0089_gray_code;
 mod n0090_subsets_ii;
+mod n0091_decode_ways;
+mod n0092_reverse_linked_list_ii;
+mod n0093_restore_ip_addresses;
+mod n0094_binary_tree_inorder_traversal;
diff --git a/src/n0091_decode_ways.rs b/src/n0091_decode_ways.rs
@@ -0,0 +1,50 @@
+/**
+ * [91] Decode Ways
+ *
+ * A message containing letters from A-Z is being encoded to numbers using the following mapping:
+ * 
+ * 
+ * 'A' -> 1
+ * 'B' -> 2
+ * ...
+ * 'Z' -> 26
+ * 
+ * 
+ * Given a non-empty string containing only digits, determine the total number of ways to decode it.
+ * 
+ * Example 1:
+ * 
+ * 
+ * Input: "12"
+ * Output: 2
+ * Explanation: It could be decoded as "AB" (1 2) or "L" (12).
+ * 
+ * 
+ * Example 2:
+ * 
+ * 
+ * Input: "226"
+ * Output: 3
+ * Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
+ * 
+ */
+pub struct Solution {}
+
+// submission codes start here
+
+impl Solution {
+    pub fn num_decodings(s: String) -> i32 {
+        0
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_91() {
+    }
+}
diff --git a/src/n0092_reverse_linked_list_ii.rs b/src/n0092_reverse_linked_list_ii.rs
@@ -0,0 +1,52 @@
+/**
+ * [92] Reverse Linked List II
+ *
+ * Reverse a linked list from position m to n. Do it in one-pass.
+ * 
+ * Note: 1 &le; m &le; n &le; length of list.
+ * 
+ * Example:
+ * 
+ * 
+ * Input: 1->2->3->4->5->NULL, m = 2, n = 4
+ * Output: 1->4->3->2->5->NULL
+ * 
+ * 
+ */
+pub struct Solution {}
+use super::util::linked_list::{ListNode, to_list};
+
+// submission codes start here
+
+// Definition for singly-linked list.
+// #[derive(PartialEq, Eq, Debug)]
+// pub struct ListNode {
+//   pub val: i32,
+//   pub next: Option<Box<ListNode>>
+// }
+// 
+// impl ListNode {
+//   #[inline]
+//   fn new(val: i32) -> Self {
+//     ListNode {
+//       next: None,
+//       val
+//     }
+//   }
+// }
+impl Solution {
+    pub fn reverse_between(head: Option<Box<ListNode>>, m: i32, n: i32) -> Option<Box<ListNode>> {
+        None
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_92() {
+    }
+}
diff --git a/src/n0093_restore_ip_addresses.rs b/src/n0093_restore_ip_addresses.rs
@@ -0,0 +1,33 @@
+/**
+ * [93] Restore IP Addresses
+ *
+ * Given a string containing only digits, restore it by returning all possible valid IP address combinations.
+ * 
+ * Example:
+ * 
+ * 
+ * Input: "25525511135"
+ * Output: ["255.255.11.135", "255.255.111.35"]
+ * 
+ * 
+ */
+pub struct Solution {}
+
+// submission codes start here
+
+impl Solution {
+    pub fn restore_ip_addresses(s: String) -> Vec<String> {
+        vec![]
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_93() {
+    }
+}
diff --git a/src/n0094_binary_tree_inorder_traversal.rs b/src/n0094_binary_tree_inorder_traversal.rs
@@ -0,0 +1,61 @@
+/**
+ * [94] Binary Tree Inorder Traversal
+ *
+ * Given a binary tree, return the inorder traversal of its nodes' values.
+ * 
+ * Example:
+ * 
+ * 
+ * Input: [1,null,2,3]
+ *    1
+ *     \
+ *      2
+ *     /
+ *    3
+ * 
+ * Output: [1,3,2]
+ * 
+ * Follow up: Recursive solution is trivial, could you do it iteratively?
+ * 
+ */
+pub struct Solution {}
+
+// submission codes start here
+
+use super::util::tree::{TreeNode, to_tree};
+use std::rc::Rc;
+use std::cell::RefCell;
+impl Solution {
+    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
+        let mut res = Vec::new();
+        Solution::inorder_traverse(root.as_ref(), &mut (|v| {res.push(v)}));
+        res
+    }
+
+    fn inorder_traverse<F: FnMut(i32)>(root: Option<&Rc<RefCell<TreeNode>>>, consumer: &mut F) {
+        if let Some(node) = root {
+            Solution::inorder_traverse(node.borrow().left.as_ref(), consumer);
+            consumer(root.as_ref().unwrap().borrow().val);
+            Solution::inorder_traverse(node.borrow().right.as_ref(), consumer);
+        }
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_94() {
+        assert_eq!(
+            Solution::inorder_traversal(tree![1,null,2,3]),
+            vec![1,3,2]
+        );
+        assert_eq!(
+            Solution::inorder_traversal(tree![1,2,3,4,5,6,7]),
+            vec![4,2,5,1,6,3,7]
+        );
+    }
+}
diff --git a/src/util/mod.rs b/src/util/mod.rs
@@ -2,3 +2,5 @@
 pub mod linked_list;
 #[macro_use]
 pub mod vec_string;
+#[macro_use]
+pub mod tree;
diff --git a/src/util/tree.rs b/src/util/tree.rs
@@ -0,0 +1,58 @@
+use std::rc::Rc;
+use std::cell::RefCell;
+
+#[derive(Debug, PartialEq, Eq)]
+pub struct TreeNode {
+    pub val: i32,
+    pub left: Option<Rc<RefCell<TreeNode>>>,
+    pub right: Option<Rc<RefCell<TreeNode>>>,
+}
+
+impl TreeNode {
+    #[inline]
+    pub fn new(val: i32) -> Self {
+        TreeNode {
+            val,
+            left: None,
+            right: None
+        }
+    }
+}
+
+pub fn to_tree(vec: Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
+    use std::collections::VecDeque;
+    let head = Some(Rc::new(RefCell::new(TreeNode::new(vec[0].unwrap()))));
+    let mut queue = VecDeque::new();
+    queue.push_back(head.as_ref().unwrap().clone());
+
+    for children in vec[1..].chunks(2) {
+        let parent = queue.pop_front().unwrap();
+        if let Some(v) = children[0] {
+            parent.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(v))));
+            queue.push_back(parent.borrow().left.as_ref().unwrap().clone());
+        }
+        if children.len() > 1 {
+            if let Some(v) = children[1] {
+                parent.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(v))));
+                queue.push_back(parent.borrow().right.as_ref().unwrap().clone());
+            }
+        }
+    }
+    head
+}
+
+#[macro_export]
+macro_rules! tree {
+    () => {
+        None
+    };
+    ($($e:expr),*) => {
+        {
+            let vec = vec![$(stringify!($e)), *];
+            let vec = vec.into_iter().map(|v| v.parse::<i32>().ok()).collect::<Vec<_>>();
+            to_tree(vec)
+        }
+    };
+    ($($e:expr,)*) => {(tree![$($e),*])};
+}
+
