Problem: 979. 在二叉树中分配硬币
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
这道题目要求我们计算在给定的二叉树中,移动硬币使每个节点恰好有一个硬币所需的最小步数。每个节点的值表示该节点上的硬币数量,而我们的目标是通过移动硬币使得每个节点都恰好有1个硬币。
解题方法
定义一个内部类Info来存储每个子树的节点数量(cnts)、硬币数量(sum)和移动硬币的步数(moves)。然后,从根节点开始,使用递归函数f遍历整棵树,对于每一个节点,我们先递归处理其左右子树,得到子树的相关信息。之后,根据子树的节点数和硬币数,我们可以计算出当前节点处硬币的盈余或短缺情况,并将其转换为移动步数的一部分。最后返回整个树的总移动步数。
复杂度
时间复杂度:
O ( n ) O(n) O(n),其中nn是二叉树中的节点数。因为我们需要访问树中的每个节点一次。
空间复杂度:
O ( h ) O(h) O(h),其中hh是二叉树的高度。这是由于递归过程中栈的深度取决于树的高度。
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public class Info{
public int cnts;
public int sum;
public int moves;
public Info(int cnts, int sum, int moves) {
this.cnts = cnts;
this.sum = sum;
this.moves = moves;
}
}
public int distributeCoins(TreeNode root) {
return f(root).moves;
}
public Info f(TreeNode x) {
if(x == null) {
return new Info(0, 0, 0);
}
Info infol = f(x.left);
Info infor = f(x.right);
int cnts = infol.cnts + infor.cnts + 1;
int sum = infol.sum + infor.sum + x.val;
int moves = infol.moves + infor.moves + Math.abs(infol.cnts - infol.sum) + Math.abs(infor.cnts - infor.sum);
return new Info(cnts, sum, moves);
}
}