<div>
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:
<pre>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. </pre>
Example 2:
<pre>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. </pre>
Constraints:
- The number of nodes in the tree is
n. 1 <= n <= 1000 <= Node.val <= n- The sum of all
Node.valisn.
</div>
题目大意：
二叉树某些节点含有硬币，求将这些硬币推向其他节点，使得所有节点都有一个硬币，求总移动次数
解题思路：
先思考，若硬币都在root，也就是求所有节点的路径和。可以用每个节点的路径和求和，也可以定义dfs返回节点数，用全局变量加左右数，每轮递归都加一次，所以每个节点被加了其路径长度的次数。本算法采用后者
下面思考若硬币不在root，由于硬币可以从儿子给父亲，这是双向的，所以dfs定义为儿子给父亲的硬币数，若节点没有硬币，返回值会是负数，也就是父亲给儿子硬币，此时这个负数正是以此节点为root的数的总的节点数，所以与上述定义一致。
所以返回root.val + left + right - 1，left和right都是负数，left + right - 1是树的大小的负数，此结果为剩余硬币推给父亲的硬币数
res += abs(left) + abs(right)左子树和右子树所有节点一起走一条边的路径和
解题步骤：
N/A
注意事项：
- dfs定义为儿子给父亲的硬币数(若有硬币)，同时是子树的节点数的负数(若无硬币)
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def 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)
