2673. 使二叉树所有路径值相等的最小代价

leetcode-2673. 使二叉树所有路径值相等的最小代价

class Solution {
public:
    int minIncrements(int n, vector<int> &cost) {
        int ans = 0;
        for (int i = n / 2; i; i--) { // 从最后一个非叶节点开始算
            ans += abs(cost[i * 2 - 1] - cost[i * 2]); // 两个子节点变成一样的
            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2]); // 累加路径和
        }
        return ans;
    }
};

这道题是第一次参加周赛的最后一题，因为时间限制没时间实现。

事后复盘发现了问题，想得还是太复杂，虽然已经明白了路径形成的过程，通过模拟也能得到正确结果。

但是显然只需要计算两个子节点的最大值即可

代码来自灵神。