[LeetCode] 979. Distribute Coins in Binary Tree

[grandyang]

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins and there are n coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (A move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.

Example 3:

Input: root = [1,0,2]
Output: 2

Example 4:

Input: root = [1,0,0,null,3]
Output: 4

Constraints:

• The number of nodes in the tree is n.
• 1 <= n <= 100
• 0 <= Node.val <= n
• The sum of Node.val is n.

这道题给了一棵二叉树，说是结点值代表硬币的个数，且每个结点可以给其相连的子结点或者父结点传硬币，现在假设硬币的总个数和结点的总个数相同，但是分布不均匀，问需要移动多少次硬币可以使每个结点上正好只有一个硬币。这道题其实难度还不小，关键看脑子能否转过一个弯来，一般人可以开始会从根结点来分析，假如硬币值大于1了，知道有多余的硬币可以传给其他的结点，如果是1，就不用变，若是0，表示需要从子结点传个结点过来，若子结点有多余的硬币还好说，若子结点也是0呢，那么子结点本身也需要别人给传硬币，这个硬币还有可能是从根结点的另一个子树中的某个位置传过来。感觉一下子好混乱，找不出规律，瞬间失去了思路，有时候从根结点分析不出来的话，就要试试从叶结点开始分析，就像之前那道 Binary Tree Cameras 一样，因为叶结点没有子结点了，它要是硬币不够，只能从父结点获得，它要是多余了硬币，也只能传给唯一的父结点（除非该叶结点就是根结点）。不管是给还是要，都是算一次移动，本质没有太大的区别，不需要分开统计，直接加在一起就行。为了方便起见，就当作每个结点都会给出当前结点值减1个的硬币，若当前是0的话，就给出 -1 个，其实就是要一个。这样每个结点可以给出的硬币的总个数就是左右子结点分别可以给出的个数加上当前结点值并减1，这就找出规律了，而且根据遍历的顺序可以知道这是二叉树的后序遍历，不管什么顺序的遍历，用递归来写都很简单。在递归函数中，先判空，若为空则返回0。否则分别对左右子结点调用递归函数并将结果保存在变量 left 和 right 中，返回值就是要给出的硬币个数，由于可能存在负数，表示需要得到，但是不管得到还是给出都是移动，所以将二者的绝对值加起来，再加到结果 res 中，然后返回当前结点需要给出的硬币总数，前面也提到了，就是左右子结点分别可以给出的个数加上当前结点值并减1，参见代码如下：

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

Github 同步地址:

#979

类似题目：

Sum of Distances in Tree

Binary Tree Cameras

参考资料：

https://leetcode.com/problems/distribute-coins-in-binary-tree/

https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/221930/JavaC%2B%2BPython-Recursive-Solution

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

LeetCode All in One 题目讲解汇总(持续更新中...)