solve #111

aylei · aylei · commit 158eca37de61 · 2019-02-13T12:03:16.000+08:00
diff --git a/src/lib.rs b/src/lib.rs
@@ -111,3 +111,4 @@ mod n0107_binary_tree_level_order_traversal_ii;
 mod n0108_convert_sorted_array_to_binary_search_tree;
 mod n0109_convert_sorted_list_to_binary_search_tree;
 mod n0110_balanced_binary_tree;
+mod n0111_minimum_depth_of_binary_tree;
diff --git a/src/n0111_minimum_depth_of_binary_tree.rs b/src/n0111_minimum_depth_of_binary_tree.rs
@@ -0,0 +1,60 @@
+/**
+ * [111] Minimum Depth of Binary Tree
+ *
+ * Given a binary tree, find its minimum depth.
+ * 
+ * The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
+ * 
+ * Note: A leaf is a node with no children.
+ * 
+ * Example:
+ * 
+ * Given binary tree [3,9,20,null,null,15,7],
+ * 
+ * 
+ *     3
+ *    / \
+ *   9  20
+ *     /  \
+ *    15   7
+ * 
+ * return its minimum depth = 2.
+ * 
+ */
+pub struct Solution {}
+use super::util::tree::{TreeNode, to_tree};
+
+// submission codes start here
+
+use std::rc::Rc;
+use std::cell::RefCell;
+use std::collections::VecDeque;
+impl Solution {
+    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
+        if root.is_none() { return 0 }
+        let mut deq = VecDeque::new();
+        deq.push_back((1, root.clone()));
+        while !deq.is_empty() {
+            if let Some((level, Some(node))) = deq.pop_front() {
+                if node.borrow().left.is_none() && node.borrow().right.is_none() {
+                    return level
+                }
+                deq.push_back((level+1, node.borrow().left.clone()));
+                deq.push_back((level+1, node.borrow().right.clone()));
+            }
+        }
+        0
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_111() {
+        assert_eq!(Solution::min_depth(tree![3,9,20,null,null,15,7]), 2);
+    }
+}
