LeetCode Entry

979. Distribute Coins in Binary Tree

18.05.2024 medium 2024 kotlin rust

Min moves to spread the coins across the tree

979. Distribute Coins in Binary Tree medium blog post substack youtube https://youtu.be/-bec2qToKoM

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/606

Problem TLDR

Min moves to spread the coins across the tree #medium #dfs #tree

Intuition

Let’s observe some examples: Some observations:

• each coin moves individually, even if we move 2 coins at once, it makes no difference to the total moves
• eventually, every node will have exactly 1 coin We can use abstract flow:
• 0 coins at leaves have flow = -1, because they are attracting coin
• flow is accumulating from children to parent, so we can compute it independently for the left and right nodes
• total moves count is sign-independent sum of total flow: we count both negative and positive moves

Approach

• for Rust there is an interesting way to use Option in combinations with ? operation that will return None; it helps to reduce the code size

Complexity

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

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

Code

    fun distributeCoins(root: TreeNode?): Int {
        var res = 0
        fun dfs(n: TreeNode?): Int = n?.run {
          (dfs(left) + dfs(right) + `val` - 1).also { res += abs(it) }} ?: 0
        dfs(root)
        return res
    }

    pub fn distribute_coins(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(n: &Option<Rc<RefCell<TreeNode>>>, res: &mut i32) -> Option<i32> {
            let n = n.as_ref()?; let n = n.borrow();
            let flow = dfs(&n.left, res).unwrap_or(0) + dfs(&n.right, res).unwrap_or(0) + n.val - 1;
            *res += flow.abs(); Some(flow)
        }
        let mut res = 0; dfs(&root, &mut res); res
    }