【每日一题】- 2020-02-21 - 979. 在二叉树中分配硬币

[azl397985856]

给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。

在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。

返回使每个结点上只有一枚硬币所需的移动次数。

 

示例 1：

输入：[3,0,0]
输出：2
解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。
示例 2：

输入：[0,3,0]
输出：3
解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。然后，我们把一枚硬币从根结点移到右子结点上。
示例 3：

输入：[1,0,2]
输出：2
示例 4：

输入：[1,0,0,null,3]
输出：4
 

提示：

1<= N <= 100
0 <= node.val <= N

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distribute-coins-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[azl397985856]

【图解】DFS（Python3）

思路

我们定义函数DFS(node)，其功能在于计算以node为顶点的子树的需要多少硬币才平衡，正数表示我有多余，负数表示我需要别人给我硬币。

我们知道一颗子树要想平衡，那么其节点的node.val之和应该等于节点的总数，因此以node为顶点的子树的需要多少硬币才平衡就等价于node.val + l + r - 1,其中l是 dfs(node.left), r是dfs(node.right)。 而我们的目标是求解移动多少步，才能使得树的金币平衡。

如下图： 实际上，我们需要移动的步骤就是abs(3) + abs(-1) + abs(2) + abs(-1) + abs(2) + abs(0)也就是 8步。

其正确性也容易证明，比如子节点的4，那么其一定有3个需要运出去的，并且我们只能运到父节点，然后父节点再看要不要继续转运。节点为0表示我们需要有一个从父节点转运过来，如果父节点不够它再管父节点或者另一个子节点要。因此我们只需要计算一共管别人要了多少次就行了，这恰好就是图中连线上的数字之和。

（图来自： https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/221939/C%2B%2B-with-picture-post-order-traversal）

代码

class Solution:

    def distributeCoins(self, root: TreeNode) -> int:
        self.cnt = 0

        def dfs(node):
            if not node:
                return 0
            l = dfs(node.left)
            r = dfs(node.right)
            self.cnt += abs(l) + abs(r)

            return node.val + l + r - 1
        dfs(root)
        return self.cnt

复杂度分析

• 时间复杂度：$O(N)$，其中N为节点的个数
• 空间复杂度：$O(H)$，其中H为树的深度

欢迎关注我的公众号《脑洞前端》获取更多更新鲜的LeetCode题解

[ZHAOXIN009]

C++ version
Runtime: 8 ms, faster than 60.13% of C++ online submissions for Distribute Coins in Binary Tree.
Memory Usage: 13.1 MB, less than 94.44% of C++ online submissions for Distribute Coins in Binary Tree.

class Solution {
    private:
    int res=0;
public:
    int helper(TreeNode* root){
        if(root==NULL) return 0;
        int left=helper(root->left);
        int right=helper(root->right);
        res+=abs(left)+abs(right);
        return root->val+left+right-1;
    }
    int distributeCoins(TreeNode* root) {
        int temp=helper(root);
        return res;
    }
};

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.