Given the root node of a binary tree where every right node is either a leaf node with a sibling (a left node that shares the same parent) or null, transform the tree so that the original leftmost node becomes the new root. Each original parent becomes the right child of its former left child, and each original right child becomes the left child of its former left sibling. Return the new root of the transformed tree.
Example 1
Input: root = TreeNode(10, TreeNode(20, TreeNode(40), TreeNode(50)), TreeNode(30))
Output: TreeNode(40, TreeNode(50), TreeNode(20, None, TreeNode(30, None, TreeNode(10))))
Explanation: The leftmost node (40) becomes the new root. The original parent nodes and right children are rearranged as specified.
Example 2
Input: root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
Output: TreeNode(4, TreeNode(5), TreeNode(2, None, TreeNode(3, None, TreeNode(1))))
Explanation: The leftmost node (4) becomes the new root. The tree is transformed accordingly.
Constraints
Case 1
Input: root = TreeNode(7, TreeNode(8, TreeNode(9), TreeNode(10)), TreeNode(11))
Expected: TreeNode(9, TreeNode(10), TreeNode(8, None, TreeNode(11, None, TreeNode(7))))
Case 2
Input: root = TreeNode(100, TreeNode(200, TreeNode(300), TreeNode(400)), TreeNode(500))
Expected: TreeNode(300, TreeNode(400), TreeNode(200, None, TreeNode(500, None, TreeNode(100))))