All problems

Flatten Binary Tree to Linked List

Medium · tree dfs

You are given the root of a binary tree. Turn it into a straight chain that only uses right children.

The chain must list the nodes in preorder: first a node itself, then everything in its left subtree, then everything in its right subtree (the same rule applies inside every subtree). In the finished chain every node's left child is empty and its right child is the next node in that preorder sequence.

Return the root of the chain. You may rearrange the existing nodes or build new ones, whichever you prefer. The first node of a preorder is always the root, so the chain starts at the original root. An empty tree stays empty.

Examples

Example 1

Input: root = [4, 2, 7, 1, 3, null, 8]

Output: [4, null, 2, null, 1, null, 3, null, 7, null, 8]

The preorder is 4, 2, 1, 3, 7, 8: node 4, then the whole left side (2, 1, 3), then the right side (7, 8).

Example 2

Input: root = [1, null, 2, 3]

Output: [1, null, 2, null, 3]

Node 2 has a left child 3. The preorder is 1, 2, 3, so 3 moves to the right of 2.

Example 3

Input: root = []

Output: []

An empty tree stays empty.

Constraints