【LetMeFly】2673.使二叉樹所有路徑值相等的最小代價(jià)：自頂向下的DFS 或 自底向上的遞推

力扣題目鏈接：https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/

給你一個(gè)整數(shù)?n?表示一棵 滿二叉樹?里面節(jié)點(diǎn)的數(shù)目，節(jié)點(diǎn)編號(hào)從 1?到 n?。根節(jié)點(diǎn)編號(hào)為 1?，樹中每個(gè)非葉子節(jié)點(diǎn)?i?都有兩個(gè)孩子，分別是左孩子?2 * i?和右孩子?2 * i + 1?。

樹中每個(gè)節(jié)點(diǎn)都有一個(gè)值，用下標(biāo)從?0?開始、長(zhǎng)度為 n?的整數(shù)數(shù)組?cost?表示，其中?cost[i]?是第?i + 1?個(gè)節(jié)點(diǎn)的值。每次操作，你可以將樹中?任意?節(jié)點(diǎn)的值?增加?1?。你可以執(zhí)行操作 任意 次。

你的目標(biāo)是讓根到每一個(gè) 葉子結(jié)點(diǎn)?的路徑值相等。請(qǐng)你返回 最少?需要執(zhí)行增加操作多少次。

注意：

• 滿二叉樹?指的是一棵樹，它滿足樹中除了葉子節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都恰好有 2 個(gè)節(jié)點(diǎn)，且所有葉子節(jié)點(diǎn)距離根節(jié)點(diǎn)距離相同。
• 路徑值 指的是路徑上所有節(jié)點(diǎn)的值之和。

?

示例 1：

輸入：n = 7, cost = [1,5,2,2,3,3,1]
輸出：6
解釋：我們執(zhí)行以下的增加操作：
- 將節(jié)點(diǎn) 4 的值增加一次。
- 將節(jié)點(diǎn) 3 的值增加三次。
- 將節(jié)點(diǎn) 7 的值增加兩次。
從根到葉子的每一條路徑值都為 9 。
總共增加次數(shù)為 1 + 3 + 2 = 6 。
這是最小的答案。

示例 2：

輸入：n = 3, cost = [5,3,3]
輸出：0
解釋：兩條路徑已經(jīng)有相等的路徑值，所以不需要執(zhí)行任何增加操作。

?

提示：

• 3 <= n <= 105
• n + 1 是?2?的冪
• cost.length == n
• 1 <= cost[i] <= 104

思路

對(duì)于某個(gè)節(jié)點(diǎn)，假設(shè)其左子樹和右子樹都已經(jīng)“增加”過了（對(duì)于左子樹，所有路徑值相等，右子樹同理），但是左子樹根到葉路徑之和（記為leftSum）和右子樹的rightSum不等，我們應(yīng)該怎么操作呢？

舉例說明點(diǎn)我

例如如下二叉樹中

   15   2
2 3 3 1

的根節(jié)點(diǎn)1，假設(shè)其左子樹已經(jīng)由

 5
2 3

變成了

 5
3 3

，而右子樹已經(jīng)由

 2
3 1

變成了

 2
3 3

那么我們應(yīng)該如何進(jìn)行下一步操作呢？

對(duì)于根節(jié)點(diǎn)1：其左子樹已經(jīng)平衡，路徑之和為5 + 3 = 8；其右子樹已經(jīng)平衡，路徑之和為2 + 3 = 5。

想要讓左右子路徑之和相等？當(dāng)然只要右子的根節(jié)點(diǎn)+3即可。

也就是說：

將左右子樹路徑和之差加到路徑和較小的子樹的根節(jié)點(diǎn)上。

這是因?yàn)椤凹右徊僮鳌痹娇拷?#xff0c;所能影響的路徑數(shù)就越多。

方法一：自頂向下的DFS

首先要說明的是這種方法的空間復(fù)雜度不如方法二，但是比方法二更容易理解。

我們只需要寫一個(gè)函數(shù)dfs(n)返回節(jié)點(diǎn)n（根節(jié)點(diǎn)下標(biāo)從0開始）為根到葉節(jié)點(diǎn)的路徑之和：

1. 遞歸左子樹得到leftSum，遞歸右子樹得到rightSum

2. 將leftSum和rightSum之差累加到答案中

3. 返回max(leftSum, rightSum) + cost[n]作為該節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑之和

終止條件：n超出數(shù)組范圍

• 時(shí)間復(fù)雜度$O(N)$，其中$N$為二叉樹節(jié)點(diǎn)個(gè)數(shù)。
• 空間復(fù)雜度$O(\log N)$，滿二叉樹的深度是$\log N$級(jí)別的。

AC代碼

C++

class Solution {
private:int ans;int dfs(int n, vector<int>& cost) {if (n >= cost.size()) {return 0;}/*01   23 4 5 6*/int leftSum = dfs(n * 2 + 1, cost);int rightSum = dfs(n * 2 + 2, cost);ans += max(leftSum, rightSum) - min(leftSum, rightSum);return max(leftSum, rightSum) + cost[n];}
public:int minIncrements(int n, vector<int>& cost) {ans = 0;dfs(0, cost);return ans;}
};

方法二：自底向上的遞推

在自頂向下的方法一中，遞歸占用了$O(N)$的空間復(fù)雜度。因?yàn)橥掠?jì)算的過程中還要存儲(chǔ)當(dāng)前節(jié)點(diǎn)的信息。

因此我們可以倒過來，采用自底向上的方法：

1. 從最后一個(gè)非葉節(jié)點(diǎn)開始往根節(jié)點(diǎn)遍歷

2. 這個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)之差累加到答案

3. 這個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)的最大值累加到這個(gè)節(jié)點(diǎn)（路徑累加）

這樣相當(dāng)于是把值存放到$cost$數(shù)組中了。

• 時(shí)間復(fù)雜度$O(N)$，其中$N$為二叉樹節(jié)點(diǎn)個(gè)數(shù)。
• 空間復(fù)雜度$O(1)$，但是我們修改了$cost$數(shù)組的值。若其值不能被修改，則空間復(fù)雜度為$O(N)$（大于方法一的$O(\log N)$，因?yàn)榉椒ㄒ坏撞康闹迪蛏蟼鬟f后可以被丟棄）

AC代碼

C++

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

Python

# from typing import Listclass Solution:def minIncrements(self, n: int, cost: List[int]) -> int:ans = 0for i in range(n // 2 - 1, -1, -1):ans += abs(cost[i * 2 + 1] - cost[i * 2 + 2])cost[i] += max(cost[i * 2 + 1], cost[i * 2 + 2])return ans

同步發(fā)文于CSDN和我的個(gè)人博客，原創(chuàng)不易，轉(zhuǎn)載經(jīng)作者同意后請(qǐng)附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136357361