111. Minimum Depth of Binary Tree Easy

1/**
2 * [111] Minimum Depth of Binary Tree
3 *
4 * Given a binary tree, find its minimum depth.
5 * The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
6 * Note: A leaf is a node with no children.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg" style="width: 432px; height: 302px;" />
10 * Input: root = [3,9,20,null,null,15,7]
11 * Output: 2
12 *
13 * Example 2:
14 *
15 * Input: root = [2,null,3,null,4,null,5,null,6]
16 * Output: 5
17 *
18 *  
19 * Constraints:
20 *
21 * The number of nodes in the tree is in the range [0, 10^5].
22 * -1000 <= Node.val <= 1000
23 *
24 */
25pub struct Solution {}
26#[allow(unused_imports)]
27use crate::util::tree::{to_tree, TreeNode};
28
29// problem: https://leetcode.com/problems/minimum-depth-of-binary-tree/
30// discuss: https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
31
32// submission codes start here
33
34// Definition for a binary tree node.
35// #[derive(Debug, PartialEq, Eq)]
36// pub struct TreeNode {
37//   pub val: i32,
38//   pub left: Option<Rc<RefCell<TreeNode>>>,
39//   pub right: Option<Rc<RefCell<TreeNode>>>,
40// }
41//
42// impl TreeNode {
43//   #[inline]
44//   pub fn new(val: i32) -> Self {
45//     TreeNode {
46//       val,
47//       left: None,
48//       right: None
49//     }
50//   }
51// }
52use std::cell::RefCell;
53use std::cmp;
54use std::rc::Rc;
55impl Solution {
56    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
57        Self::_min_depth(root.as_ref())
58    }
59
60    pub fn _min_depth(root: Option<&Rc<RefCell<TreeNode>>>) -> i32 {
61        match root {
62            Some(r) => {
63                let right = Self::_min_depth(r.borrow().right.as_ref());
64                let left = Self::_min_depth(r.borrow().left.as_ref());
65                if right == 0 || left == 0 {
66                    1 + cmp::max(right, left)
67                } else {
68                    1 + cmp::min(right, left)
69                }
70            }
71            None => 0,
72        }
73    }
74}
75
76// submission codes end
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81    use crate::tree;
82
83    #[test]
84    fn test_111() {
85        assert_eq!(2, Solution::min_depth(tree![3,9,20,null,null,15,7]));
86        assert_eq!(5, Solution::min_depth(tree![2,null,3,null,4,null,5,null,6]));
87    }
88}
89