Show problems as
Classic problem #1038MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Binary Search Tree to Greater Sum Tree

Real-world version: Heavier Snowfall Totals
Tracked in this browser only
Read Binary Search Tree to Greater Sum Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ski patrol files every snowfall it has measured, in centimetres, in a binary search tree keyed by the depth: for any filed fall, every depth in the branch to its left is smaller and every depth in the branch to its right is larger. No two filed falls share a depth.

The tree arrives as records, a level-order listing. The first entry is the depth at the head of the tree. After that, the listing gives the first branch then the second branch of each record already listed, in the order those records appear, writing null wherever a branch is empty. Slots below a null are never written down, and the trailing run of null entries is left off.

The patrol wants each record restated as a heavier-fall total: the depth of that fall plus the depths of every strictly greater fall on file. So a depth of 12 filed alongside depths 30 and 45 is restated as 12 + 30 + 45, and the greatest depth on file is restated as itself.

Rewrite every record with its heavier-fall total. The shape of the tree does not change, only the numbers written in it, and the rewritten numbers are generally no longer in search-tree order.

Return the rewritten tree in the same level-order form: null for an empty branch, nothing written below a null, and no trailing null entries.

Examples

Example 1

Input
records = [30, 12, 45, 6, 18, 40, 60]
Output
[175, 205, 105, 211, 193, 145, 60]

The filed depths are 6, 12, 18, 30, 40, 45 and 60, which add up to 211. The record at the head holds 30, and 30 with the heavier depths 40, 45 and 60 comes to 175, so that slot reports 175. The 60 has nothing heavier on file and reports 60, while the lightest depth 6 picks up everything and reports 211.

Example 2

Input
records = [7]
Output
[7]

One record is on file and nothing is heavier than it, so it reports its own depth of 7.

Example 3

Input
records = [1, null, 5, null, 6]
Output
[12, null, 11, null, 6]

Every record here hangs off the second branch of the one above it, giving depths 1, 5 and 6. The 6 reports 6, the 5 reports 5 + 6 = 11 and the 1 reports 1 + 5 + 6 = 12. The shape is untouched, so the two nulls stay exactly where they were.

Constraints

  • The number of records in the tree is in the range [1, 100].
  • 1 <= records.length <= 200
  • 0 <= records[i] <= 100
  • An entry of records that is null marks an empty branch rather than a record.
  • records[0] is never null, and no depth appears twice.
  • Every heavier-fall total therefore stays at or below 5050.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def rewrite_snow_records(records: list[int | None]) -> list[int | None]:
Java
public Integer[] rewriteSnowRecords(Integer[] records)

More on the same topics