#114
Flatten Binary Tree to Linked List
Medium Morris-style rewiring
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Flatten a binary tree into a "linked list" in place, using right pointers in preorder order and setting every left pointer to null.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: turn the tree into a right-only chain in preorder.
Why this works: at each node with a left child, attach the right subtree to the end of the left subtree, then move the left subtree to the right.
Example: 1 (2 (3, 4), 5 (-, 6))
1 → 2 → 3 → 4 → 5 → 6✦Hints open one at a time
For a node with a left subtree, its right subtree should come after the rightmost node of the left subtree.
Attach the right subtree there, move the left subtree to the right, and continue.
↗Approach
Walk down the right spine. At each node with a left child: find the rightmost node of the left subtree, set its right to node.right, move node.left to node.right, and clear node.left.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public void flatten(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode pre = cur.left;
while (pre.right != null) pre = pre.right; // end of the left subtree in preorder
pre.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
}!Common mistake
Forgetting to set left to null — the judge checks it.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon