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

关键词：层序遍历、深度优先

题目起源：6419. 使二叉树所有门路值相等的最小代价 - 力扣（Leetcode）

题目形容

 T层序遍历 T深度优先

给你一个整数 n 示意一棵 满二叉树 外面节点的数目，节点编号从 1 到 n 。根节点编号为 1 ，树中每个非叶子节点 i 都有两个孩子，别离是左孩子 2 * i 和右孩子 2 * i + 1 。

树中每个节点都有一个值，用下标从 0 开始、长度为 n 的整数数组 cost 示意，其中 cost[i] 是第 i + 1 个节点的值。每次操作，你能够将树中 任意 节点的值 减少 1 。你能够执行操作 任意 次。

你的指标是让根到每一个 叶子结点 的门路值相等。请你返回 起码 须要执行减少操作多少次。

  • 满二叉树 指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个节点，且所有叶子节点间隔根节点间隔雷同。
  • 门路值 指的是门路上所有节点的值之和。

奢侈实现

不难想到，最终根节点到各叶子结点的门路值必然等于最后根节点到各叶子结点的最大门路值。

于是，先通过深搜，将各叶子结点到根节点的门路值预处理进去，同时找出最大门路值。之后，便能够失去各叶子结点门路值与指标门路值（即找到的最大门路值）的差值，这个差值即为对这个叶子结点须要进行的操作数。

同时，又发现，具备雷同父结点的两个兄弟结点l和r，给l和r加上x，等价于给l和r的父结点+x，于是，可将对最初一层结点（叶子结点所在层）的操作进行压缩，对于倒数第二层，同样能够进行相似的操作压缩，直到压缩到根节点。

int minIncrements(int n, vector<int> &cost) {    /**     * 深度优先遍历：计算出每个叶子节点的门路值，并找出最大门路值     */    int d[n + 1], maxDep = 0;    memset(d, 0, sizeof d);    function<void(int, int)> dfs = [&](int u, int dep) {        int t = dep + cost[u - 1];        if (u > n >> 1) {            d[u] = t, maxDep = max(t, maxDep);            return;        }        dfs(u << 1, t), dfs(u << 1 | 1, t);    };    dfs(1, 0);    // 计算出每个叶子结点的门路值与最大门路值的差值    for (int i = (n >> 1) + 1; i <= n; i++)d[i] = maxDep - d[i];    /**     * 设左孩子、右孩子、父结点的门路值别离为l、r、p     * 因为往父结点+v，等价于往左右孩子各+v     * 所以，无妨把左右孩子加的公共值加到父结点上，从而减小操作次数     * 也即（假如l≤r），p=min(l,r)，l=0，r=-=l     * 逐层将操作往上传递     */    int res = 0;    while (n > 1) {        for (int i = (n >> 1) + 1; i <= n; i += 2) {            if (d[i] || d[i + 1]) {                if (d[i] > d[i + 1])swap(d[i], d[i + 1]);                d[i >> 1] = d[i];           // 公共操作施加到父结点                res += d[i + 1] - d[i];     // 进行非公共操作            }        }        n >>= 1;    }    return res;}

工夫复杂度：O(n)

空间复杂度：O(n)

精简实现

精简实现的外围与奢侈实现雷同，都是操作压缩，只是做法略微更难想一点。

思考一棵只有三个结点的满二叉树，设左右孩子结点为l、r，父结点为p，f(x)示意以结点x为根节点的满二叉树，使x到其各叶子结点的门路值相等后，x到叶子结点的门路值，显然，对于叶子结点，f(x)=结点值，假如f(l)<f(r)，要想使p到叶子结点l和r的门路值相等，只须要令f(l)等于f(r)，也即f(l)始终加到f(r)就能够了。

思考两棵下面这样的满二叉树，父结点别离为p1和p2，通过下面的操作，p1到l1和r1的间隔曾经相等，即有f(p1)，p2到l2和r2的间隔曾经相等，即有f(p2)，假如f(p1)＜f(p2)，设p1和p2的父结点为p，要想使结点p到各叶子结点的门路值相等，只须要令f(p1)等于f(p2)，也即f(p1)始终加到f(p2)即可。

依此类推，逐层往上合并，直到根节点。

int minIncrements(int n, vector<int> &cost) {    int res = 0;    for (int i = n - 2; i > 0; i -= 2) {        if (cost[i] < cost[i + 1])swap(cost[i], cost[i + 1]);        res += cost[i] - cost[i + 1], cost[i >> 1] += cost[i];    }    return res;}

工夫复杂度：O(n)

空间复杂度度：O(1)