Skip to content

2673. Make Costs of Paths Equal in a Binary Tree 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int minIncrements(int n, vector<int>& cost) {
    int ans = 0;

    for (int i = n / 2 - 1; i >= 0; --i) {
      const int l = i * 2 + 1;
      const int r = i * 2 + 2;
      ans += abs(cost[l] - cost[r]);
      // Record the information in the parent from the children. So, there's
      // need to actually update the values in the children.
      cost[i] += max(cost[l], cost[r]);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int minIncrements(int n, int[] cost) {
    int ans = 0;

    for (int i = n / 2 - 1; i >= 0; --i) {
      final int l = i * 2 + 1;
      final int r = i * 2 + 2;
      ans += Math.abs(cost[l] - cost[r]);
      // Record the information in the parent from the children. So, there's need to actually
      // update the values in the children.
      cost[i] += Math.max(cost[l], cost[r]);
    }

    return ans;
  }
}

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

    for i in range(n // 2 - 1, -1, -1):
      l = i * 2 + 1
      r = i * 2 + 2
      ans += abs(cost[l] - cost[r])
      # Record the information in the parent from the children. So, there's need to actually
      # update the values in the children.
      cost[i] += max(cost[l], cost[r])

    return ans