114. Flatten Binary Tree to Linked List ๐
Last updated
Last updated
Difficulty: Medium
- Tags: Binary Tree
, Depth-First Search (DFS)
, Linked List
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode
class where:
The right child pointer points to the next node in the list.
The left child pointer is always null
.
The "linked list" should follow the pre-order traversal of the binary tree.
๐น Example 1:
Input:
Output:
Explanation:
The binary tree:
is flattened to:
๐น Example 2:
Input:
Output:
๐น Example 3:
Input:
Output:
The number of nodes in the tree is in the range [0, 2000]
.
-100 <= Node.val <= 100
.
Can you flatten the tree in-place (using O(1)
extra space)?
To solve this problem:
Use pre-order traversal to flatten the tree into a linked list.
Modify the TreeNode
pointers in-place to achieve O(1)
space complexity.
Traversal:
Start from the root and traverse down the tree using the right child.
Rearranging Nodes:
For each node:
If it has a left child, locate the rightmost node in the left subtree.
Attach the right subtree to the rightmost node.
Move the left subtree to the right and set the left child to null
.
In-place Modification:
The tree is modified directly without using any extra space.
O(n): Each node is visited once.
O(1): The tree is modified in-place without any extra data structures.
How would you approach the problem using recursion?
Can you adapt this solution to work for a general graph structure?
You can find the full solution here.