979. 在二叉树中分配硬币 (opens new window)

1.后序遍历

单纯找到“富余”节点，然后找到空硬币节点，最后计算移动次数。这种做法完全做不出来，因为这其中还涉及到如何移动到“最近空硬币节点”的问题。

本题目的难点在于如何抽象搬运过程简化移动次数统计？

• 遍历时，考虑当前节点需要取出的硬币个数。如果为负数则表示当前节点需要放入硬币。

• dfs(root)：返回以root节点作为根节点的子树总共需要“取出的硬币数量”。其中主要进行了两个操作：

  1. 统计移动次数：无论是放入还是取出一个节点，统计时都需要移动。Math.abs(dfs(root.left))表示左子树取出/放入的所有硬币放到当前root节点需要的步数。
  2. 盈亏抵消：左节点与右节点多出的与缺少的硬币数量，再加上root节点“贡献的”硬币数量，在root节点处进行加减正负抵消。

这样的做法之所以答案是正确的，原因在于：自底向上遍历+正负抵消法保证了当前资金流的流向是唯一的，因此当前统计的移动步数是最小的。

• 这里唯一性指的是，假设Math.abs(dfs(root.right))>0

  • 如果左子树是取出(正流向)，那么只能将所有多余的硬币放到父节点。统计的步数是将多的硬币从子节点放到父节点的步数。
  • 如果左子树是放入(负流向)，那么只能将外面多余的金币放入左子树。统计的步数是将父节点多余硬币放入左子树的步数。

  因此资金流向总是流向父节点的。

• 这里“最小”指的是全局步数最小。考虑一种情况【1，1，1，2，0，2，0】，可以证明，在优先满足子树再满足邻居的分配方案下，全局移动步数是最小的。

class Solution {
    int res=0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root){
        if(root==null) return 0;
        int l=dfs(root.left);
        int r=dfs(root.right);
        res+=Math.abs(l);
        res+=Math.abs(r);
        return l+r+(root.val-1);

    }
}