算法leetcode

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

字数统计: 964字   |   阅读时长: 3分
, ,

摘要: 二叉树的遍历

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们来看一个二叉树遍历的问题。算法非常基础，主要是想到在 DFS 的过程中递归地维护各个子树的最长路径长度，基于这个长度我们计算出最终要求的目标。

题目

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

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

你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。

注意：

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

提示：

1
2
3
4
3 <= n <= 1e5
n + 1 是 2 的幂
cost.length == n
1 <= cost[i] <= 1e4

示例 1：

输入：n = 7, cost = [1,5,2,2,3,3,1]
输出：6
解释：我们执行以下的增加操作：

  • 将节点 4 的值增加一次。
  • 将节点 3 的值增加三次。
  • 将节点 7 的值增加两次。
    从根到叶子的每一条路径值都为 9 。
    总共增加次数为 1 + 3 + 2 = 6 。
    这是最小的答案。

示例 2：

输入：n = 3, cost = [5,3,3]
输出：0
解释：两条路径已经有相等的路径值，所以不需要执行任何增加操作。

题解

算法: DFS

对于一棵树来说，任意一条从根节点到叶子结点的路径中，根节点都是共用的，因此如果向左走的最长路径与向右走的最长路径不一样的话，改根节点的值没用，需要改左子树或右子树中的节点才行。比如向左走的最长路径更长的话，就需要修改右子树中的节点。

从根节点开始 DFS，记以 $u$ 为根的子树上的最长路径为 $f[u]$，假设左子节点和右子节点分别为 $l$ 和 $r$，先递归地遍历 $l$ 和 $r$，返回 $f[l]$ 和 $f[r]$，这样就有：

为了使得 $f[l]$ 等于 $f[r]$，只需要将最长路径较小的子树的根节点增加 $abs(f[l] - f[r])$ 即可。原因在于从节点 $u$ 回溯时，递归的处理过程已经保证了 $u$ 代表的子树中所有路径的和相同，这样如果要增加 $u$ 子树的路径和，增加根节点可以让树种所有路径都达成变化，因此增加的次数最少。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        self.ans = 0
        self.cost = cost
        self.n = n
        self.preOrder(1)
        return self.ans

    def preOrder(self, node: int) ->int:
        # 返回以 node 为根的子树，最长路径的和
        if node * 2 > self.n:
            return self.cost[node - 1]
        left = node * 2
        right = node * 2 + 1
        left_sum = self.preOrder(left)
        right_sum = self.preOrder(right)
        self.ans += abs(left_sum - right_sum)
        return max(left_sum, right_sum) + self.cost[node - 1]
Share