LeetCode-in-All
543. Diameter of Binary Tree
Easy
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -100 <= Node.val <= 100
Solution
// Definition for a binary tree node.
// 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;
use std::cmp::max;
impl Solution {
pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut diameter = 0;
fn helper(root: Option<Rc<RefCell<TreeNode>>>, diameter: &mut i32) -> (i32, i32) {
if let Some(root) = root {
let (l1, l2) = helper(root.borrow().left.clone(), diameter);
let (r1, r2) = helper(root.borrow().right.clone(), diameter);
*diameter = max(*diameter, l1 + l2);
*diameter = max(*diameter, r1 + r2);
let l = l1.max(l2) + 1;
let r = r1.max(r2) + 1;
return (l, r);
}
// (depth, diameter that doesn't pass through )
(-1, -1)
}
let (l, r) = helper(root, &mut diameter);
diameter = max(diameter, l + r);
diameter
}
}