MediumNeetCode150Linked ListStackTreeDepth-First SearchBinary Tree
Flatten Binary Tree to Linked List
Flatten to right-skewed tree.
Examples
Input
root = [1,2,5,3,4,null,6]
Output
[1,null,2,null,3,null,4,null,5,null,6]
Preorder as right children.
Constraints
- •
Number of nodes in [0,2000] - •
-100 <= Node.val <= 100
Approaches
Store preorder, rebuild.
CodeT: O(n) | S: O(n) store
Process right, left, root.
CodeT: O(n) | S: O(n) stack
In-place without extra space.
CodeT: O(n) | S: O(1) space
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(n) | O(n) store | Store preorder, rebuild. |
| Reverse Postorder | O(n) | O(n) stack | Process right, left, root. |
| Threaded Binary Tree | O(n) | O(1) space | In-place without extra space. |
Recursion
T: O(n)S: O(n) store
Store preorder, rebuild.
Reverse Postorder
T: O(n)S: O(n) stack
Process right, left, root.
Threaded Binary Tree
T: O(n)S: O(1) space
In-place without extra space.
Common Mistakes
Not handling null root
Losing right subtree
Not flattening completely