solve #104

aylei · aylei · commit f5c52714036b · 2019-02-12T19:53:41.000+08:00
diff --git a/src/lib.rs b/src/lib.rs
@@ -104,3 +104,4 @@ mod n0100_same_tree;
 mod n0101_symmetric_tree;
 mod n0102_binary_tree_level_order_traversal;
 mod n0103_binary_tree_zigzag_level_order_traversal;
+mod n0104_maximum_depth_of_binary_tree;
diff --git a/src/n0104_maximum_depth_of_binary_tree.rs b/src/n0104_maximum_depth_of_binary_tree.rs
@@ -0,0 +1,58 @@
+/**
+ * [104] Maximum Depth of Binary Tree
+ *
+ * Given a binary tree, find its maximum depth.
+ * 
+ * The maximum depth is the number of nodes along the longest path from the root node down to the farthest 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 depth = 3.
+ * 
+ */
+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 max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
+        let mut max = 0;
+        Solution::depth_helper(root.as_ref(), &mut max, 0);
+        max
+    }
+
+    fn depth_helper(root: Option<&Rc<RefCell<TreeNode>>>, max: &mut i32, curr: i32) {
+        if let Some(node) = root {
+            *max = i32::max(*max, curr + 1);
+            Solution::depth_helper(node.borrow().left.as_ref(), max, curr + 1);
+            Solution::depth_helper(node.borrow().right.as_ref(), max, curr + 1);
+        }
+    }
+}
+
+// submission codes end
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_104() {
+        assert_eq!(Solution::max_depth(tree![]), 0);
+        assert_eq!(Solution::max_depth(tree![3,9,20,null,null,15,7]), 3);
+    }
+}
