root of a binary tree. Its **left spine** is the chain made of the root, its left child, that node's left child, and so on until there are no more left children. The bottom node of the left spine is guaranteed to have no right child.
Flip the tree along its left spine. For every spine node that has a left child L:
- L becomes the parent of that node;
- the node itself becomes the **right** child of L;
- the node's former right child (if any) becomes the **left** child of L, moving together with its whole subtree, which stays unchanged inside.
As a result, the bottom node of the left spine turns into the new root. Return it. An empty tree stays empty.root=tree_node([5, 8, 3, 6, 9]) → [6, 9, 8, None, None, 3, 5]
The leftmost node 6 becomes the root, its sibling 9 becomes its left child and its parent 8 its right child. Then 8 gets 3 on the left and the old root 5 on the right.
root=tree_node([4, 2, None, 7]) → [7, None, 2, None, 4]
There are no right children at all, so the left path 4 → 2 → 7 simply turns into the right path 7 → 2 → 4.
root=tree_node([1, 2, 3, 4, None, 5, 6]) → [4, None, 2, 3, 1, 5, 6]
The new root is 4. It has no sibling, so its left child is empty and its right child is 2. Node 2 gets 3 on the left together with its whole subtree (5 and 6 stay with it), and 1 on the right.
Node.val ≤ 1000root=tree_node([5, 8, 3, 6, 9])
[6, 9, 8, None, None, 3, 5]
Run checks the first 3 tests in your browser. Submit checks all 57 tests on the server, hidden ones included.