542. Turn-by-Turn Directions
A hiking park maps its trail junctions as a binary tree rooted at root: from a junction you can walk to its left branch, to its right branch, or back up toward the entrance. A ranger stands at the junction labelled start and must reach the junction labelled dest by the shortest route, taking each branch at most once.
Return the route as a string of moves: 'U' for one step up to the parent, 'L' for one step down to the left child and 'R' for one step down to the right child. The route always climbs first and then descends, so the string is some number of 'U' characters followed by a mix of 'L' and 'R'.
Both start and dest exist in the tree and they are different.
Example 1
- Input:
- root = [8,3,10,1,6,null,14,null,null,4,7,13]start = 4dest = 13
- Output:
- "UUURRL"
- Explanation:
From 4 go up to 6, 3 and 8 (three U moves), then down to 10, 14 and 13 (R, R, L).
Example 2
- Input:
- root = [8,3,10,1,6,null,14,null,null,4,7,13]start = 1dest = 7
- Output:
- "URR"
- Explanation:
Go up once from 1 to reach 3, then down to 6 (R) and to 7 (R).
Example 3
- Input:
- root = [8,3,10,1,6,null,14,null,null,4,7,13]start = 14dest = 10
- Output:
- "U"
- Explanation:
Node 10 is the parent of 14, so a single U move is enough.
Constraints
2 ≤ number of nodes ≤ 105
1 ≤ Node.val ≤ 106, all values distinct
start and dest are values present in the tree, and start ≠ dest
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)