Repeatedly Delete Leaves Matching a Target Value From a Binary Tree

Given a binary tree and an integer target, delete every leaf whose value equals target. Deleting a leaf can turn its parent into a leaf; if that parent's value also equals target, it must be deleted as well, and so on, until no leaf with value target remains. Return the resulting tree, which is empty if the root itself ends up deleted.

Function Signature

remove_target_leaves(tree: list[int | None], target: int) -> list[int | None]

Tree Encoding

The input and the output use the same level-order encoding:

• An empty tree is [].
• Otherwise the first element is the root's value. Present nodes are then visited in breadth-first order, left to right, and for each one its left child and then its right child are appended, using None for an absent child. Children of absent nodes are not listed.
• Trailing None values are omitted.

The input list is always well formed, and the output must be in exactly this canonical form.

Rules

• A leaf is a node with no children.
• A node whose value equals target but that still has at least one child after all deletions is kept.
• Kept nodes never move: every kept node keeps its original parent and its side (left or right).
• The returned tree contains no leaf whose value equals target.

Constraints

• The input tree has between 1 and 5000 nodes, and its height is at most 500.
• Node values and target are integers in [-1000000000, 1000000000].

Examples

Input: tree = [5,7,7,7,3,None,7], target = 7

Output: [5,7,None,None,3]

The leaf 7 under the root's left child is deleted, but that left child still has the child 3, so it stays. On the right side, deleting the lower 7 turns the root's right child into a leaf with value 7, so it is deleted too.

Input: tree = [3,3,1], target = 3

Output: [3,None,1]

Only the left leaf is deleted. The root's value is 3, but it still has a child.

Input: tree = [4,4,4], target = 4

Output: []