leetcode题解-979-在二叉树中分配硬币

发表于

题目

官方way

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int ans;
    public int distributeCoins(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode node) {
        if (node == null) return 0;
        int L = dfs(node.left);
        int R = dfs(node.right);
        ans += Math.abs(L) + Math.abs(R);
        return node.val + L + R - 1;
    }
}

一种抽象的思维：

  • 抽象：硬币数 \(\rightarrow\) 负载量，考虑成: \(一个节点的负载量 = abs(硬币数-1)\)
  • 节点间的硬币的移动数量: abs(dfs(node->left)) + abs(dfs(node->right))

Reference

https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/solution/zai-er-cha-shu-zhong-fen-pei-ying-bi-by-leetcode/