Leetcode 2673. Make Costs of Paths Equal in a Binary Tree

[Woodyiiiiiii]

2673. Make Costs of Paths Equal in a Binary Tree

2673. Make Costs of Paths Equal in a Binary Tree

这道题一看就知道是从下至上，归并贪心，树上DFS(不算树上DP)。

我在竞赛中用了比较长的思考时间，先算出最大路径，然后用尽量把两颗子树差值往上递增的思想，最后写了很长一段。

那么简单做法是原地修改节点值，然后用全局变量计算子树差值。原地修改成最大值，目的是贪心的思想，暗含了上一段的想法。

class Solution {
    public int minIncrements(int n, int[] cost) {
        int ans = 0;
        for (int i = n / 2 - 1; i >= 0; i--) {
            ans += Math.abs(cost[2 * i + 1] - cost[2 * i + 2]);
            cost[i] += Math.max(cost[2 * i + 1], cost[2 * i + 2]);
        }
        return ans;
    }
}