leetcode_for_rust/cd0111_minimum_depth_of_binary_tree/
mod.rs

1//! Minimum Depth of Binary Tree[leetcode: minimum_depth_of_binary_tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/)
2//!
3//! Given a binary tree, find its minimum depth.
4//!
5//!The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
6//!
7//! **Note:** A leaf is a node with no children.
8//!
9//! **example:**
10//! Given binary tree `[3,9,20,null,null,15,7]`,
11//!
12//! ```
13//!     3
14//!    / \
15//!   9  20
16//!     /  \
17//!    15   7
18//! ```
19//! return its depth = 2.
20
21use std::rc::Rc;
22use std::cell::RefCell;
23use std::cmp::Ord;
24/// # Solutions
25///
26/// # Approach 1: DFS
27///
28/// * Time complexity: O(n)
29///
30/// * Space complexity: O(1)
31///
32/// * Runtime: 0 ms
33///
34/// * Memory: 3.1 MB
35///
36/// ```rust
37/// // Definition for a binary tree node.
38/// // #[derive(Debug, PartialEq, Eq)]
39/// // pub struct TreeNode {
40/// //   pub val: i32,
41/// //   pub left: Option<Rc<RefCell<TreeNode>>>,
42/// //   pub right: Option<Rc<RefCell<TreeNode>>>,
43/// // }
44/// //
45/// // impl TreeNode {
46/// //   #[inline]
47/// //   pub fn new(val: i32) -> Self {
48/// //     TreeNode {
49/// //       val,
50/// //       left: None,
51/// //       right: None
52/// //     }
53/// //   }
54/// // }
55/// use std::rc::Rc;
56/// use std::cell::RefCell;
57/// use std::cmp::Ord;
58/// impl Solution {
59///     pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
60///         match root {
61///             Some(node) => {
62///                 let left = Self::min_depth(node.borrow().left.clone());
63///                 let right = Self::min_depth(node.borrow().right.clone());
64///
65///                 if left == 0 || right == 0 {
66///                     1 + left + right
67///                 } else {
68///                     1 + left.min(right)
69///                 }
70///             },
71///             _ => 0,
72///         }
73///     }
74/// }
75/// ```
76///
77/// # Approach 2: BFS
78///
79/// * Time complexity: O(n)
80///
81/// * Space complexity: O(1)
82///
83/// * Runtime: 0 ms
84///
85/// * Memory: 3.2 MB
86///
87/// ```rust
88/// // Definition for a binary tree node.
89/// // #[derive(Debug, PartialEq, Eq)]
90/// // pub struct TreeNode {
91/// //   pub val: i32,
92/// //   pub left: Option<Rc<RefCell<TreeNode>>>,
93/// //   pub right: Option<Rc<RefCell<TreeNode>>>,
94/// // }
95/// //
96/// // impl TreeNode {
97/// //   #[inline]
98/// //   pub fn new(val: i32) -> Self {
99/// //     TreeNode {
100/// //       val,
101/// //       left: None,
102/// //       right: None
103/// //     }
104/// //   }
105/// // }
106/// use std::rc::Rc;
107/// use std::cell::RefCell;
108/// use std::collections::VecDeque;
109/// impl Solution {
110///     pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
111///         if root.is_none() { return 0; }
112///
113///         let mut deque: VecDeque<Option<Rc<RefCell<TreeNode>>>> = VecDeque::new();
114///         let mut depth = 0;
115///         deque.push_back(root);
116///
117///         while !deque.is_empty() {
118///             depth += 1;
119///             let mut added = false;
120///             let level_size = deque.len();
121///
122///             for _i in 0..level_size {
123///                 let n = deque.pop_front();
124///                 if let(Some(Some(node))) = n {
125///                     added = true;
126///                     if node.borrow().left.is_none() && node.borrow().right.is_none() { return depth; }
127///                     if node.borrow().left.is_some() { deque.push_back(node.borrow().left.clone()); }
128///                     if node.borrow().right.is_some() { deque.push_back(node.borrow().right.clone());}
129///                 }
130///             }
131///             if !added { break; }
132///         }
133///         depth
134///     }
135/// }
136/// ```
137///
138pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
139    match root {
140        Some(node) => {
141            let left = min_depth(node.borrow().left.clone());
142            let right = min_depth(node.borrow().right.clone());
143
144            if left == 0 || right == 0 {
145                1 + left + right
146            } else {
147                1 + left.min(right)
148            }
149        },
150        _ => 0,
151    }
152}
153// Definition for a binary tree node.
154#[derive(Debug, PartialEq, Eq)]
155pub struct TreeNode {
156  pub val: i32,
157  pub left: Option<Rc<RefCell<TreeNode>>>,
158  pub right: Option<Rc<RefCell<TreeNode>>>,
159}
160
161impl TreeNode {
162  #[inline]
163  pub fn new(val: i32) -> Self {
164    TreeNode {
165      val,
166      left: None,
167      right: None
168    }
169  }
170}
leetcode_for_rust/cd0111_minimum_depth_of_binary_tree/mod.rs

leetcode_for_rust/cd0111_minimum_depth_of_binary_tree/
mod.rs
