Flatten Binary Tree to Linked List
Problem Description
Given the root of a binary tree, flatten the tree into a "linked list":
- The "linked list" should use the same
TreeNodeclass where therightchild pointer points to the next node in the list and theleftchild pointer is alwaysnull. - The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Example 1:
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [0]
Output: [0]
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Follow up: Can you flatten the tree in-place (with O(1) extra space)?
Solve it on LeetCode
Approaches
1. Preorder Traversal and Reconnection
Intuition:
The basic idea is to perform a preorder traversal of the tree and store the nodes in a list. Then, modify the pointers of each node in the list to flatten the tree into a linked list. This method is straightforward but uses extra space.
Steps:
- Perform a preorder traversal using a recursive function.
- Store each visited node in a list.
- Iterate through the list and adjust the left and right pointers to flatten the tree.
Code:
- Time Complexity: O(N), where N is the number of nodes. Each node is visited once.
- Space Complexity: O(N), since we store all nodes in a list.
2. Iterative with Stack
Intuition:
This approach uses a stack to simulate the recursion stack used in preorder traversal. By iterating with a stack, we can avoid using additional space for storing nodes.
Steps:
- Use a stack to maintain the nodes to be processed.
- Push the root node onto the stack.
- While the stack is not empty, pop the node, process it, and push its children.
- Adjust the left and right pointers as you traverse each node.
Code:
- Time Complexity: O(N), each node is visited once.
- Space Complexity: O(N), in the worst case, the stack can have all the nodes of a skewed tree.
3. Morris Traversal
Intuition:
Morris traversal modifies the tree structure during the traversal and is based on threaded binary trees. It allows traversal without using extra space other than a few pointers.
Steps:
- For each node, if it has a left child, find the rightmost node in its left subtree.
- Redirect the rightmost node's right pointer to the current node's right child.
- Move the current node to its left, then set the left to null.
- Continue to the right of the current node.
Code:
- Time Complexity: O(N), every node is visited at most twice.
- Space Complexity: O(1), no additional data structures are used.