LeetCode 979 Distribute Coins in Binary Tree

LeetCode

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.

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

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

Example 1:

Input: root = [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: root = [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.

Constraints:

The number of nodes in the tree is n. 1 <= n <= 100
0 <= Node.val <= n The sum of all Node.val is n.

题目大意：

二叉树某些节点含有硬币，求将这些硬币推向其他节点，使得所有节点都有一个硬币，求总移动次数

解题思路：

先思考，若硬币都在root，也就是求所有节点的路径和。可以用每个节点的路径和求和，也可以定义dfs返回节点数，用全局变量加左右数，每轮递归都加一次，所以每个节点被加了其路径长度的次数。本算法采用后者
下面思考若硬币不在root，由于硬币可以从儿子给父亲，这是双向的，所以dfs定义为儿子给父亲的硬币数，若节点没有硬币，返回值会是负数，也就是父亲给儿子硬币，此时这个负数正是以此节点为root的数的总的节点数，所以与上述定义一致。
所以返回root.val + left + right - 1，left和right都是负数，left + right - 1是树的大小的负数，此结果为剩余硬币推给父亲的硬币数
res += abs(left) + abs(right)左子树和右子树所有节点一起走一条边的路径和

解题步骤：

N/A

注意事项：

1. dfs定义为儿子给父亲的硬币数(若有硬币)，同时是子树的节点数的负数(若无硬币)

Python代码：

def distributeCoins(self, root: TreeNode) -> int:
	res = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal res
		left = dfs(root.left)
		right = dfs(root.right)
		res += abs(left) + abs(right)
		return root.val + left + right - 1

	dfs(root)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)