Flatten the Tree Into a Right-Leaning Chain
Implement flattenInPreorder
You are given the root of a binary tree. Rearrange it in place — reusing the same nodes — into a "chain" that leans to the right: every node has no left child, and its right child is the node that comes next in the pre-order traversal of the original tree (node, then its left subtree, then its right subtree). Return the root of the rearranged tree.
You could record the pre-order in a list and then relink the nodes, but the rearrangement can also be done with a single pointer walking down the chain, splicing each right subtree behind the last node of the left subtree.
Example 1:
Input: root = [12,6,15,3,9,null,18]
Output: [12,null,6,null,3,null,9,null,15,null,18]
Example 2:
Input: root = [4,2]
Output: [4,null,2]
Example 3:
Input: root = []
Output: []
+ 11 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100 - ●
−100 ≤ node.val ≤ 100 - ●
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ●
Rearrange the tree IN PLACE (reuse the same nodes) so that every node has no left child and its right child is the next node in the pre-order of the original tree (node, then its left subtree, then its right subtree). Return the root. The result is checked as a level-order list
root =