14.04.2024
404. Sum of Left Leaves easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/571
Problem TLDR
Left-leaf sum in a Binary Tree #easy
Intuition
Do a Depth-First Search and check if left node is a leaf
Approach
Let’s try to reuse the original method’s signature.
in Rust
Rc::clone
is a cheap operation
Complexity
Time complexity:
O(n)Space complexity:
O(log(n)), for the recursion stack space
Code
fun sumOfLeftLeaves(root: TreeNode?): Int = root?.run {
(left?.takeIf { it.left == null && it.right == null }?.`val` ?:
sumOfLeftLeaves(left)) + sumOfLeftLeaves(right)
} ?: 0
pub fn sum_of_left_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
root.as_ref().map_or(0, |n| { let n = n.borrow();
n.left.as_ref().map_or(0, |left| { let l = left.borrow();
if l.left.is_none() && l.right.is_none() { l.val }
else { Self::sum_of_left_leaves(Some(Rc::clone(left))) }
}) +
n.right.as_ref().map_or(0, |r| Self::sum_of_left_leaves(Some(Rc::clone(r))))
})
}