A trail company represents each of its hiking networks as a binary branching tree of junctions. Starting from the trailhead (the root), every junction either dead-ends at a scenic overlook -- a leaf with no further branches -- or splits into a left-continuing trail, a right-continuing trail, or both. Every junction and overlook carries a numeric code.
Two trail maps are called twin routes if, reading their overlooks strictly left to right, they list the exact same sequence of overlook codes -- regardless of how differently the two networks branch to get there. You are given two trail maps; determine whether they are twin routes.
Each trail map is given as a level-order listing of its junction codes, using -1 to mark a missing child (the standard array encoding of a binary tree: after the root, every junction that was actually placed in the tree contributes exactly two entries, for its left and right child slots in order, where -1 means that slot is empty).
Print true if the two trail maps are twin routes, or false otherwise.
Example 1
Input
11 1 2 3 4 5 -1 -1 -1 -1 -1 -1 11 9 8 3 4 5 -1 -1 -1 -1 -1 -1
Expected
true
Explanation
The first map's listing builds a tree with root 1, children 2 and 3, and 2's children 4 and 5; its overlooks left to right are 4, 5, 3. The second map's listing builds a differently shaped tree -- root 9 with children 8 and 3, and 8's children 4 and 5 -- whose overlooks left to right are also 4, 5, 3. Since both sequences match exactly, the maps are twin routes: true.
Example 2
Input
11 1 2 3 4 5 -1 -1 -1 -1 -1 -1 11 9 8 3 4 6 -1 -1 -1 -1 -1 -1
Expected
false
Explanation
The first map is the same as in Example 1, with overlook sequence 4, 5, 3. The second map's listing gives overlooks 4, 6, 3 -- the middle overlook is 6 instead of 5. Because the sequences differ, the maps are not twin routes: false.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →