题目链接：
题解
树形 DP，每一个节点最后对答案贡献是左右子树路径 sum 的差。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #
# @lc app=leetcode.cn id=2673 lang=python3
#
# [2673] 使二叉树所有路径值相等的最小代价
#
# @lc code=start
class Solution:
def minIncrements(self, n: int, cost: List[int]) -> int:
# ans = 0
def dfs(rt, n):
if rt > n:
return 0, 0
now_ans = 0
left, ans = dfs(rt*2, n)
now_ans += ans
right, ans = dfs(rt*2+1, n)
now_ans += ans
now_ans += abs(left-right)
return max(left, right) + cost[rt-1], now_ans
sum1, ans = dfs(1, n)
return ans
# @lc code=end
|