root of a binary tree. Rebuild it into a chain made of the same nodes:
- every node's left link is None;
- the right link points to the next node of the chain, and the last node's is None;
- the nodes follow preorder: a node first, then its left subtree, then its right subtree.
Rewire the existing nodes rather than creating new ones, and return the head of the chain — the old root (None for an empty tree).
Can you do it with O(1) extra memory?root=tree_node([7, 3, 9, 1, None, None, 4]) → [7, None, 3, None, 1, None, 9, None, 4]
The preorder is 7, 3, 1, 9, 4. After the call the tree is the chain 7 → 3 → 1 → 9 → 4 along right links, with every left link None.
root=tree_node([5, 2, None, -6]) → [5, None, 2, None, -6]
The tree leans left: 5 → 2 → -6. The nodes move to the right side, giving the chain 5 → 2 → -6.
root=tree_node([]) → None
An empty tree: nothing to change.
root=tree_node([7, 3, 9, 1, None, None, 4])
[7, None, 3, None, 1, None, 9, None, 4]
Run checks the first 3 tests in your browser. Submit checks all 34 tests on the server, hidden ones included.