979. 在二叉树中分配硬币
题意
- 移动硬币使得每个节点只有一枚硬币
- 子节点可以向父节点移动硬币,父节点也可以向子节点移动硬币
解法 递归实现
树的题目一般都是递归到叶子节点,然后向上回溯实现的。
因此,假设中间节点 root
,以其左右孩子为根的子树都已经实现了每节点一个硬币,且其左孩子拥有的硬币数为 l
,其右孩子拥有的硬币数为 r
,那么,左孩子需要移动 l - 1
枚硬币到父节点,右孩子需要移动 r - 1
枚硬币到父节点,其左右孩子共移动 abs(l) + abs(r)
次硬币,其父节点共有 l + r - root->val
枚硬币。
move
函数返回当前节点需要移动给父节点的硬币数,即 l + r - root->val - 1
枚。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int move(TreeNode* root, int& ans){if(root == nullptr) return 0; // 需要移动的次数// ans += abs(move(root->left, ans)) + abs(move(root->right, ans));int moveLeft = move(root->left, ans);int moveRight = move(root->right, ans);ans += abs(moveLeft) + abs(moveRight);// cout<<moveLeft<<" "<<moveRight<<" "<<ans<<" "<<moveLeft + moveRight + root->val - 1<<endl;return moveLeft + moveRight + root->val - 1;// return move(root->left, ans) + abs(move(root->right, ans)) + root->val - 1;}int distributeCoins(TreeNode* root) {int ans = 0;move(root, ans);return ans;}
};
ATTENTION
- 不能直接
return move(root->left, ans) + abs(move(root->right, ans)) + root->val - 1;
,这样会多次重复修改ans
的值,导致结果错误。
复杂度分析
时间复杂度 O(N):每个节点遍历一遍。
空间复杂度 O(N):递归深度与二叉树的深度有关,二叉树深度最小为 logN,最大为 N。