[路飞]_leetcode-979-在二叉树中分配硬币

「这是我参与2022首次更文挑战的第29天，活动详情查看：2022首次更文挑战」

[题目地址][B站地址]

给定一个有 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. 1<= N <= 100
2. 0 <= node.val <= N

解题思路

首先，我们可以将本题所求的移动次数拆分为每个结点上所需的移动次数。

接下来的问题就是如何求每个结点上所需的移动次数？

因为本题要求每个结点上只有一枚硬币，如果当前结点是叶子结点：

1. 如果该结点没有硬币，则需要移动过来一枚硬币
2. 如果该结点的硬币数量大于 1，则需要移走 node.val-1 枚硬币

上面的移动硬币数量也就是该结点位置所需的移动次数。

那如果当前结点不是叶子结点呢？

这个时候就需要知道其左右子树的情况

1. 如果左右子树的硬币数量是有多余的，则会给到当前结点一定数量的硬币，如果该硬币数量加上当前节点的 node.val 大于 1，则当前结点需要将多余的硬币继续向上移动
2. 如果左右子树的硬币数量是不够的，则需要向当前结点索取一定数量的硬币，如果当前结点没有，则需要向它的父结点索取

这里我们假设左右子树返回的数量为 l，r，如果值为 0,则说明该子树不需要索取硬币，也没有多余硬币，如果为正数，则说明该子树硬币有多余，如果为负数，则说明该子树硬币不够。

基于以上条件，当前节点向上返回的值应该是 l+r+node.val-1，而当前节点所需的移动次数是 l+r+node.val-1 的绝对值，因为不管是索取还是向上给予，都需要对应的移动次数。

基于以上分析，很明显本题需要递归处理二叉树中的每一个结点，并在回溯的过程中基于子树返回的信息确定当前结点的操作次数，所以我们需要采用前序遍历处理二叉树。

代码实现

var distributeCoins = function (root) {
  // 初始化结果值为 0
  let res = 0
  // 前序遍历二叉树
  function preorder(node) {
    // 如果当前节点为空节点，不需要操作次数，返回 0
    if (node === null) return 0
    // 获取左右子树返回的值，对应其多余或需要的硬币数量
    const l = preorder(node.left),
      r = preorder(node.right),
    // 计算当前结点多余或所需的硬币数量
    step = l + r + node.val - 1;
    // 记录操作次数
    res += Math.abs(step)
    // 返回当前节点值
    return step
  }
  // 调用前序遍历处理二叉树
  preorder(root)
  // 返回结果值
  return res
}
复制代码

至此我们就完成了 leetcode-979-在二叉树中分配硬币

如有任何问题或建议，欢迎留言讨论！👏🏻👏🏻👏🏻