LeetCode 979题二叉树分硬币C++解法核心逻辑疑问

先看votrubac的C++后序遍历实现代码：

int traverse(TreeNode* r, int &moves) {
  if (r == nullptr) return 0;
  int left = traverse(r->left, moves), right = traverse(r->right, moves);
  moves += abs(left) + abs(right); // <----- 核心疑问点
  return r->val + left + right - 1;
}
int distributeCoins(TreeNode* r, int moves = 0) {
  traverse(r, moves);
  return moves;
}

首先明确核心逻辑：traverse函数的返回值代表当前子树与父节点之间需要传递的硬币数量——正数表示当前子树有多余硬币，要向上传给父节点；负数表示当前子树缺少硬币，需要从父节点获取。

疑问解答 #

1. 为什么当前子树中要执行moves += abs(left) + abs(right)？ #

left是左子树与当前节点的硬币传递量：如果left为正，说明左子树多了left个硬币，需要移动left次到当前节点；如果为负，说明左子树缺abs(left)个硬币，需要从当前节点移动abs(left)次过去。不管是送还是拿，移动次数都是绝对值。同理right是右子树与当前节点的移动次数。这两部分加起来，就是当前节点处理左右子树硬币平衡时产生的总移动次数，所以要累加到moves中。

2. 为什么不需要涉及当前节点，比如写成moves += abs(curr_node) + abs(left) + abs(right)？ #

当前节点的硬币状态已经被封装在返回值r->val + left + right -1里：这个值计算的是当前子树整体（含当前节点）的硬币盈余/缺口。当前节点与父节点之间的移动次数，会在父节点的abs(当前节点返回值)中被统计，这里如果再加当前节点的相关值，会导致重复计算。比如当前节点最后要给父节点2个硬币，这个移动次数会在父节点处理时被算入moves，不需要在这里提前统计。

3. 这是否意味着每个子树的移动次数仅等于左、右子树的移动次数之和？ #

不是。每个子树的总移动次数由两部分组成：

• 左、右子树内部的移动次数（这部分已经在递归遍历左右子树时累加到moves里了）
• 左、右子树与当前节点之间的移动次数（也就是这里的abs(left)+abs(right)）

所以当前子树对总移动次数的贡献，是左右子树内部的移动次数，加上当前节点与左右子树的交互次数，并非仅等于左右子树的移动次数之和。

4. 在根节点子树中，moves += abs(left) + abs(right)，难道根节点没有移动次数？是否由abs(left)或abs(right)覆盖？ #

根节点没有父节点，所以它不需要和任何父节点传递硬币，自然没有这部分的移动次数。而根节点与左右子树之间的移动次数，已经被abs(left)+abs(right)统计到moves里了。另外，整个树的硬币总数等于节点数，所以根节点的返回值r->val + left + right -1必然是0（没有盈余也没有缺口），不需要再处理任何额外移动。根节点的所有相关移动需求，都已经被左右子树与它的交互次数覆盖了。

内容的提问来源于stack exchange，提问作者kenpeter