Description
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.
给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回使每个结点上只有一枚硬币所需的移动次数。
题目链接：https://leetcode.com/problems/distribute-coins-in-binary-tree/
Difficulty: medium
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<= N <= 100
- 0 <= node.val <= N
分析
- 每一次递归记录当前节点的硬币变化情况：如left是左节点多出的硬币，right是右节点多出的硬币，index是当前节点多出的硬币；
- 用全局变量Sum记录硬币移动的次数；
- 返回Sum。
参考代码
Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def distributeCoins(self, root):
if(root==None):
return 0
Sum=0
def _iter(ro):
left=0
if(ro.left!=None):
left=_iter(ro.left)
right=0
if(ro.right!=None):
right=_iter(ro.right)
index=ro.val+left+right-1
nonlocal Sum
Sum+=abs(left)
Sum+=abs(right)
return index
_iter(root)
return Sum