LeetCode Entry

1325. Delete Leaves With a Given Value

17.05.2024 easy 2024 kotlin rust

Recursively remove target leafs from the tree

1325. Delete Leaves With a Given Value easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/605

Problem TLDR

Recursively remove target leafs from the tree #easy #dfs #tree

Intuition

When dealing with Binary Trees try to solve the subproblem recursively.

Approach

• Notice how drop is used in Rust, without it borrow checker would not allow to return Some(node)

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(log(n))\) for the recursion depth

Code

    fun removeLeafNodes(root: TreeNode?, target: Int): TreeNode? = root?.run {
        left = removeLeafNodes(left, target)
        right = removeLeafNodes(right, target)
        if (left == null && right == null && `val` == target) null else root
    }

    pub fn remove_leaf_nodes(root: Option<Rc<RefCell<TreeNode>>>, target: i32) -> Option<Rc<RefCell<TreeNode>>> {
        let node = root?; let mut n = node.borrow_mut();
        n.left = Self::remove_leaf_nodes(n.left.take(), target);
        n.right = Self::remove_leaf_nodes(n.right.take(), target);
        if n.left.is_none() && n.right.is_none() && n.val == target { None } else { drop(n); Some(node) }
    }