Show problems as
Classic problem #2196MediumArrayHash TableTreeBinary Tree

Create Binary Tree From Descriptions

Real-world version: Retracing the Heating Network
Tracked in this browser only
Read Create Binary Tree From Descriptions on LeetCode(opens in a new tab)

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

A survey crew has re-traced a district heating network one connection at a time, in no particular order. Each note links[i] = [upstream_i, downstream_i, tap_i] says that valve downstream_i hangs directly off valve upstream_i: off that valve's left tap when tap_i is 1, and off its right tap when tap_i is 0.

Valve ids are distinct positive integers. Every valve has at most one valve on its left tap and at most one on its right tap, and the notes together describe a single network with exactly one valve at the top, which is the one no note ever lists as a downstream valve.

Rebuild the network and return it as a flat listing, laid out by this rule and no other. Put the top valve into a waiting line on its own. Then repeatedly take the valve at the front of the line: write its id at the end of the listing, then add to the back of the line what sits on its left tap and then what sits on its right tap, adding the marker null for a tap with nothing on it. When null reaches the front of the line, write null to the listing and add nothing. Stop when the line runs dry, then delete any null entries left sitting after the last valve id in the listing.

Examples

Example 1

Input
links = [[41, 27, 1], [41, 58, 0]]
Output
[41, 27, 58]

Valve 41 is the only one no note feeds. It carries 27 on its left tap and 58 on its right, and both of those have nothing hanging off them, so the listing ends there.

Example 2

Input
links = [[3, 8, 0], [19, 3, 1], [19, 44, 0], [8, 5, 1]]
Output
[19, 3, 44, null, 8, null, null, 5]

Valve 19 is at the top even though it appears in the second note. Valve 3 has an empty left tap, which shows up as a `null` inside the listing rather than at the end.

Example 3

Input
links = [[9, 4, 1], [4, 2, 1], [2, 61, 1]]
Output
[9, 4, null, 2, null, 61]

Every connection here uses a left tap, so each valve leaves a `null` behind for the right tap it never fills, and only the run of `null` markers past the last id is deleted.

Constraints

  • 1 <= links.length <= 10^4
  • links[i].length == 3
  • 1 <= upstream_i, downstream_i <= 10^5
  • 0 <= tap_i <= 1
  • The notes describe a valid network: one top valve, at most one valve per tap, and no cycles.

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 rebuild_network(links: list[list[int]]) -> list:
Java
public List<Integer> rebuildNetwork(int[][] links)

More on the same topics