979. 在二叉树中分配硬币
2020-03-22 本文已影响0人
lazy_ccccat
题目描述
https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/
思路
这个思路我没想出来,喵了一眼答案没喵懂。
呢呢三言两语给我说懂了。
- 过载量:如果树的叶子仅包含 0 枚金币(与它所需相比,它的
过载量
为 -1),那么我们需要从它的父亲节点移动一枚金币到这个叶子节点上。如果说,一个叶子节点包含 4 枚金币(它的过载量
为 3),那么我们需要将这个叶子节点中的 3 枚金币移动给他父亲。 - 想一想,调整的过程是怎样的?从根节点开始调整,还是从叶子节点开始调整呢?比如某个二叉树,左孩子缺3个,右孩子多2个,他们的父节点root缺1个。把这三个作为一个整体。那个父节点root是不是还要向上索要(汇报)两个?意味着这个子树的缺口是2(过载量-2)。所以应该是从叶子往上开始调整,两个叶子,把自己所在子树的过载量(我缺几个,或者多几个)向上汇报,父节点来做决定,怎么分配。那么root节点向上汇报的值,肯定就是0喔。
- 注意,节点向上汇报的值,只是节点子树的过载量,并不是节点子树的移动次数哦,移动次数需另行计算(我的做法是用全局变量累加)。这就是返回值并不能直接作为结果的。
代码
class Solution {
public:
int cnt = 0;
int distributeCoins(TreeNode* root) {
dfs(root);
return this->cnt;
}
int dfs(TreeNode* root) { //算子树的过载量
if (!root) return 0;
else if (!root->left && !root->right) {
return root->val - 1;
} else {
int left = dfs(root->left);
int right = dfs(root->right);
this->cnt += abs(left) + abs(right);
return root->val + left + right - 1;
}
}
};