964.分配硬币到二叉树

分配硬币到二叉树

给定二叉树，每个节点有若干硬币（0 或正整数），硬币总数等于节点数。每次移动一枚硬币到相邻节点，返回使每个节点恰好有 1 枚硬币所需的最小移动次数。

示例 1:

输入：[0]
输出：0

示例 2:

输入：[1,0,2]
输出：2

提示:

• 树中节点数在 1 到 1000 之间
• 0 <= node.val <= 1000

解析

DFS 返回当前子树的余额（正值表示多余，负值表示不足），累加移动次数。

var distributeCoins = function (root) {
  let moves = 0;

  const dfs = (node) => {
    if (!node) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    moves += Math.abs(left) + Math.abs(right);
    return node.val + left + right - 1;
  };

  dfs(root);
  return moves;
};

时间复杂度 O(N)，空间复杂度 O(H)。