关于算法:每日一题使二叉树所有路径值相等的最小代价

30次阅读

共计 1834 个字符，预计需要花费 5 分钟才能阅读完成。

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

题目起源：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)

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

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)

正文完