Problem: 979. 在二叉树中分配硬币
思路
- 考虑最后计算成本的时候实际上是计算的是每个节点对硬币的操作数
- 每个节点只需要一个硬币,如何确定多出来的或少的硬币的流向
- 考虑自底向上,叶子节点只需要一个硬币,这样就能向父节点要硬币或者向父节点送硬币,之后父节点变成了叶子节点(其子节点已完成使命)
- 设一个值为$Need$表示需要向上移或者向上要的硬币数,根据以上推论我们能够得到如下公式,正数表示需要向上移动,负数表示需要上方向下移动 $$Need_{节点}=Need_{子节点}+val-1$$
- 每次将一个节点处理完就将Need的绝对值加入到操作数之中
Code
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.res=0
def dfs(node:TreeNode):
if node==None:
return 0
left=dfs(node.left)
right=dfs(node.right)
self.res+=abs(left)+abs(right)
return right+left+node.val-1
dfs(root)
return self.res
class Solution {
public:
int res=0;
int dfs(TreeNode* root){
if (!root) return 0;
int left=dfs(root->left);
int right=dfs(root->right);
res+=abs(left)+abs(right);
return left+right+root->val-1;
}
int distributeCoins(TreeNode* root) {
dfs(root);
return res;
}
};