LeetCode Entry
543. Diameter of Binary Tree
Max distance between any nodes in binary tree.
543. Diameter of Binary Tree easy
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/521
Problem TLDR
Max distance between any nodes in binary tree.
Intuition
Distance is the sum of the longest depths in left and right nodes.
Approach
We can return a pair of sum and max depth, but modifying an external variable looks simpler.
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(log(n))\)
Code
fun diameterOfBinaryTree(root: TreeNode?): Int {
var max = 0
fun dfs(n: TreeNode?): Int = n?.run {
val l = dfs(left); val r = dfs(right)
max = max(max, l + r); 1 + max(l, r)
} ?: 0
dfs(root)
return max
}
pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut res = 0;
fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, res: &mut i32) -> i32 {
n.as_ref().map_or(0, |n| { let n = n.borrow();
let (l, r) = (dfs(&n.left, res), dfs(&n.right, res));
*res = (*res).max(l + r); 1 + l.max(r)
})
}
dfs(&root, &mut res); res
}