Loading page…
Practice problem · easy
An online shop shows its category menu as a tree. Each category has at most two sub-categories, drawn as a left one and a right one. The shop is opening in a country that reads right to left, so the menu must be shown as its mirror image.
A mirror image swaps the left and the right sub-category of every category, at every level. The menu lists the categories in pre-order: a category first, then its left sub-menu, then its right sub-menu. A big shop has up to 100,000 categories.
Write mirror_preorder(values, left, right).
0 to n - 1, and category 0 is the top of the menu.values[i] is the id shown for category i.left[i] and right[i] are the numbers of the sub-categories of category i, or -1 where there is none.Input: values = [4, 2, 7, 1, 3], left = [1, 3, -1, -1, -1], right = [2, 4, -1, -1, -1]
Output: [4, 7, 2, 3, 1]| Step | Category visited | Stack of categories still to visit (next on the right) |
|---|---|---|
| 1 | id 4 (category 0) |
1, 2 |
| 2 | id 7 (category 2, the original right) |
1 |
| 3 | id 2 (category 1) |
3, 4 |
| 4 | id 3 (category 4, the original right of category 1) |
3 |
| 5 | id 1 (category 3) |
empty |
After the mirror, id 7 comes before id 2, and id 3 comes before id 1.
Input: values = [9], left = [-1], right = [-1]
Output: [9]One category is its own mirror image.
Input: values = [1, 2, 3], left = [1, 2, -1], right = [-1, -1, -1]
Output: [1, 2, 3]The menu is a chain going left. In the mirror it goes right, but each category still comes before the one inside it.
1 ≤ length of values = length of left = length of right ≤ 10^50 ≤ values[i] ≤ 10^6left and right is -1 or a category number from 1 to n - 10A menu that is a chain of 100,000 categories is allowed. A function that calls itself for each sub-category needs 100,000 nested calls, and Python and Java stop long before that.
Walking with a list used as a stack never nests, and it visits each category once.
mirror_preorder · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.