0979. 在二叉树中分配硬币【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 后序遍历

1. 📝 题目描述

• leetcode

给你一个有 n 个结点的二叉树的根结点 root，其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。

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

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

---

示例 1：

输入：root = [3,0,0]
输出：2

解释：
一枚硬币从根结点移动到左子结点，一枚硬币从根结点移动到右子结点。

---

示例 2：

输入：root = [0,3,0]
输出：3

解释：
将两枚硬币从根结点的左子结点移动到根结点（两次移动）。
然后，将一枚硬币从根结点移动到右子结点。

---

提示：

• 树中节点的数目为 n
• 1 <= n <= 100
• 0 <= Node.val <= n
• 所有 Node.val 的值之和是 n

2. 🎯 s.1 - 后序遍历

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var distributeCoins = function (root) {
  let moves = 0

  const dfs = (node) => {
    if (!node) return 0

    // 后序遍历：先处理左右子树
    const leftBalance = dfs(node.left)
    const rightBalance = dfs(node.right)

    // 计算当前节点的移动次数（左右子树的盈余或缺失）
    moves += Math.abs(leftBalance) + Math.abs(rightBalance)

    // 返回当前子树的盈余或缺失
    // node.val - 1 表示当前节点自己的盈余或缺失
    // leftBalance + rightBalance 表示子树传递上来的盈余或缺失
    return node.val - 1 + leftBalance + rightBalance
  }

  dfs(root)
  return moves
}

• 时间复杂度：$O(n)$，其中 n 是树中节点数量，每个节点访问一次
• 空间复杂度：$O(h)$，其中 h 是树的高度，递归栈的空间开销

算法思路：

• 后序遍历：先处理左右子树，再处理当前节点，确保子树的盈余或缺失信息向上传递
• 平衡计算：每个节点返回其子树的盈余（正数）或缺失（负数）硬币数量，计算公式为 node.val - 1 + leftBalance + rightBalance
• 移动次数：每个节点的移动次数等于其左右子树传递的硬币数量的绝对值之和 |leftBalance| + |rightBalance|
• 核心思想：每个节点最终需要保留 1 枚硬币，多余的向上传递，缺失的从上接收，经过该节点的硬币数量即为移动次数
• 返回值：每个节点向父节点返回当前子树的总盈余或缺失，供父节点计算移动次数