make-costs-of-paths-equal-in-a-binary-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer <code>n</code> representing the number of nodes in a perfect binary tree consisting of nodes numbered from <code>1</code> to <code>n</code>. The root of the tree is node <code>1</code> and each node <code>i</code> in the tree has two children where the left child is the node <code>2 * i</code> and the right child is <code>2 * i + 1</code>.

Each node in the tree also has a cost represented by a given 0-indexed integer array <code>cost</code> of size <code>n</code> where <code>cost[i]</code> is the cost of node <code>i + 1</code>. You are allowed to increment the cost of any node by <code>1</code> any number of times.

Return the minimum number of increments you need to make the cost of paths from the root to each leaf node equal.

Note:

<ul>
	<li>A perfect binary tree is a tree where each node, except the leaf nodes, has exactly 2 children.</li>
	<li>The cost of a path is the sum of costs of nodes in the path.</li>
</ul>

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreeedrawio-4.png" />
<pre>
Input: n = 7, cost = [1,5,2,2,3,3,1]
Output: 6
Explanation: We can do the following increments:
- Increase the cost of node 4 one time.
- Increase the cost of node 3 three times.
- Increase the cost of node 7 two times.
Each path from the root to a leaf will have a total cost of 9.
The total increments we did is 1 + 3 + 2 = 6.
It can be shown that this is the minimum answer we can achieve.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreee2drawio.png" style="width: 205px; height: 151px;" />
<pre>
Input: n = 3, cost = [5,3,3]
Output: 0
Explanation: The two paths already have equal total costs, so no increments are needed.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>n + 1</code> is a power of <code>2</code></li>
	<li><code>cost.length == n</code></li>
	<li><code>1 &lt;= cost[i] &lt;= 104</code></li>
</ul>

minIncrements

Make Costs of Paths Equal in a Binary Tree

Greedy

Tree

Array

Dynamic Programming

Binary Tree

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

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

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

注意：

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

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreeedrawio-4.png" />

<pre>
输入：n = 7, cost = [1,5,2,2,3,3,1]
输出：6
解释：我们执行以下的增加操作：
- 将节点 4 的值增加一次。
- 将节点 3 的值增加三次。
- 将节点 7 的值增加两次。
从根到叶子的每一条路径值都为 9 。
总共增加次数为 1 + 3 + 2 = 6 。
这是最小的答案。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2023/04/04/binaryytreee2drawio.png" style="width: 205px; height: 151px;" />

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

&nbsp;

提示：

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>n + 1</code> 是&nbsp;<code>2</code>&nbsp;的幂</li>
	<li><code>cost.length == n</code></li>
	<li><code>1 &lt;= cost[i] &lt;= 104</code></li>
</ul>