Show problems as
Classic problem #617EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Merge Two Binary Trees

Real-world version: Laying One Rig Over Another
Tracked in this browser only
Read Merge Two Binary Trees on LeetCode(opens in a new tab)

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

Two rigs are given as the flat lists root1 and root2. Each hangs from a single top joint, every joint carries at most two joints below it in a first and a second slot, and either slot may be empty.

A flat list is read level by level: its first entry is the top joint's load, and reading left to right, every entry that is not null claims the next two unused positions as its first and second slot in that order, while null marks an empty slot and claims no positions of its own. A list that ends early leaves the remaining slots empty, and an empty list means no joints at all.

Lay the second rig over the first so their top joints line up, and likewise each pair of matching slots. Where both rigs have a joint, the merged joint carries the two loads added together. Where only one has a joint, that joint and everything below it is kept as it stands.

Return the merged rig in the same flat form, with no null left trailing at the end.

Examples

Example 1

Input
root1 = [1], root2 = [2]
Output
[3]

Both rigs are a single joint, so the merged rig is one joint carrying the two loads added together.

Example 2

Input
root1 = [1], root2 = []
Output
[1]

The second rig has no joints at all, so the first is kept as it stands.

Example 3

Input
root1 = [1, null, 2], root2 = [3, 4]
Output
[4, 4, 2]

The tops add to 4. The first rig has nothing in its first slot, so the second rig's joint there is kept; the second rig has nothing in its second slot, so the first rig's joint there is kept.

Constraints

  • Each rig holds between 0 and 2000 joints.
  • 0 <= root1.length <= 6000
  • 0 <= root2.length <= 6000
  • -10000 <= root1[i] <= 10000
  • -10000 <= root2[i] <= 10000
  • The first entry of a list is not null unless the list is empty.

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 merge_trees(root1: list, root2: list) -> list:
Java
public Integer[] mergeTrees(Integer[] root1, Integer[] root2)

More on the same topics