979. Distribute Coins in Binary Tree

Problem

Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.

Example 3:

Input: [1,0,2]
Output: 2

Example 4:

Input: [1,0,0,null,3]
Output: 4

Note:

1. 1<= N <= 100
2. 0 <= node.val <= N

Problem Summary

Given the root node root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins in total. In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.) Return the number of moves required to make every node have exactly one coin.

Notes:

1. 1<= N <= 100
2. 0 <= node.val <= N

Solution Approach

• Given a tree with N nodes. There are N coins distributed among these N nodes. Ask how many moves are needed so that every node has one coin.
• At first glance, this problem seems difficult to analyze, but after thinking carefully, it can be solved using greedy and divide-and-conquer ideas. The smallest unit of a tree is a root node and its two children. In this case, among the 3 nodes, whichever node has more coins can give coins to the node without coins, and this way of moving can also guarantee the minimum number of moves. It is not hard to prove that the fewest steps come from moving coins from adjacent nodes. So for a tree, start from the lowest level and work upward, gradually moving coins from bottom to top until finally the root node also has a coin. A node with more than 1 coin is recorded as n -1, and a node with no coins is recorded as -1. For example, among the 3 nodes in the lower-left corner of the figure below, the node with 4 coins can send out 3 coins, and the leaf node with 0 coins needs to receive 1 coin. The root node has 0 coins; its left child gives 3 coins, its right child needs 1 coin, and it must keep one coin for itself, so in the end it can still have 1 coin left.

• Therefore, the number of moves for each node should be left + right + root.Val - 1. Finally, solve it recursively.

Code

package leetcode

/**
 * Definition for a binary tree root.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distributeCoins(root *TreeNode) int {
	res := 0
	distributeCoinsDFS(root, &res)
	return res
}

func distributeCoinsDFS(root *TreeNode, res *int) int {
	if root == nil {
		return 0
	}
	left, right := distributeCoinsDFS(root.Left, res), distributeCoinsDFS(root.Right, res)
	*res += abs(left) + abs(right)
	return left + right + root.Val - 1
}