Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a "linked list" in-place:

• The "linked list" should use the same TreeNode class where the right child pointer points to the next node and the left child pointer is always null.
• The "linked list" should be in the same order as a preorder traversal of the binary tree.

Examples

Example 1:

Input: root = [1, 2, 5, 3, 4, null, 6]
Output: [1, null, 2, null, 3, null, 4, null, 5, null, 6]

      1              1
     / \              \
    2   5     =>       2
   / \   \              \
  3   4   6              3
                          \
                           4
                            \
                             5
                              \
                               6

Example 2:

Input: root = []
Output: []

Constraints

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Expected Complexity

• Time: O(n)
• Space: O(1) for Morris approach, O(h) for recursive