| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Easy (77.12%) | 1655 | - |
Tags
tree | depth-first-search
Companies
apple | linkedin | uber | yahoo
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
1
2
| 输入：root = [3,9,20,null,null,15,7]
输出：3
|
示例 2：
1
2
| 输入：root = [1,null,2]
输出：2
|
提示：
- 树中节点的数量在
[0, 10<sup>4</sup>] 区间内。 -100 <= Node.val <= 100
Discussion | Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| // @lc code=start
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
/// ## 解题思路
/// - 递归
/// `max_depth = 1 + max(max_depth(left) + max_depth(right))`
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
match root {
None => 0,
Some(node) => 1 + std::cmp::max(Solution::max_depth(node.borrow().right.clone()),
Solution::max_depth(node.borrow().left.clone())),
}
}
}
// @lc code=end
|