Invert Binary Tree
Real-world version: Mirror The Splitter HarnessThe statement here is our own: the same inputs, outputs and technique.
A cable installer describes a broadcast harness as a binary tree of splitters, where each splitter has a left feed and a right feed and either may be absent.
The harness arrives as a level-order list root. Its first entry is the value at the top splitter. After that, every splitter that is present contributes its left feed and then its right feed, with null written for a feed that is absent. Nothing below an absent feed is listed, and null entries at the very end of the list are trimmed off. An empty harness is the empty list.
Rewire the harness so that at every splitter the left feed and the right feed trade places, and return the rewired harness written in the same level-order form.
Perform the rewiring by swapping the two feed links on each splitter in place. Do not assemble a second harness alongside the first.
Examples
Example 1
- Input
- root = [8,3,10,1,6,null,14]
- Output
- [8,10,3,14,null,6,1]
At the top splitter, 3 and 10 trade places. Splitter 3 held feeds 1 and 6, which trade to 6 and 1. Splitter 10 held an absent left feed and 14, which trade to 14 and absent.
Example 2
- Input
- root = [5,null,9]
- Output
- [5,9]
Splitter 5 has only a right feed of 9, so after the trade 9 becomes its left feed and its right feed is absent. The trailing `null` for that absent feed is trimmed.
Example 3
- Input
- root = [6,null,2,3]
- Output
- [6,2,null,null,3]
Splitter 6 has only a right feed of 2, which becomes its left feed. Splitter 2 has only a left feed of 3, which becomes its right feed.
Example 4
- Input
- root = [-4]
- Output
- [-4]
The single splitter has two absent feeds, and trading two absent feeds changes nothing.
Example 5
- Input
- root = [1,2,null,3]
- Output
- [1,null,2,null,3]
Splitter 1 keeps only 2, which moves to its right feed. Splitter 2 keeps only 3, which likewise moves to its right feed, so the chain now leans right the whole way down.
Constraints
- The number of splitters is in the range [0, 100].
- -100 <= splitter value <= 100
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.
def invert_tree(root: list) -> list:public TreeNode invertTree(TreeNode root)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 5 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's