※ 引述《yam276 (史萊哲林的優等生)》之銘言：
: 用Easy來玩Rust
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 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Constraints:
The number of nodes in the tree is in the range [0, 10^5]
-1000 <= Node.val <= 1000
跟max很像 但除了max改成min之外還要多判斷其中一邊為nullptr的情況
Code:
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
match root {
Some(node) => {
let mut node = node.borrow_mut();
let left_depth = Self::min_depth(node.left.clone());
let right_depth = Self::min_depth(node.right.clone());
if left_depth == 0 || right_depth == 0 {
return left_depth + right_depth + 1;
}
return std::cmp::min(left_depth, right_depth) + 1;
}
None => return 0,
}
return 0;
}
}
等價於：
class Solution
{
public:
int minDepth(TreeNode* root)
{
if (root == nullptr)
return 0;
int left_depth = minDepth(root->left);
int right_depth = minDepth(root->right);
if (!left_depth || !right_depth)
return left_depth + right_depth + 1;
return min(left_depth, right_depth) + 1;
}
};