← 返回 databricks 的题目列表Shortest Path in a Preorder-Labeled Fibonacci Tree
类型：online_judge
Problem: Shortest Path in a Preorder-Labeled Fibonacci Tree
Define a Fibonacci Tree T(n) as follows:
T(0) and T(1) are both single-node trees.
For n >= 2, the root of T(n) has two children:
left subtree: T(n-2);
right subtree: T(n-1).
All nodes in T(n) are labeled with consecutive integers starting from 1 using preorder traversal:
label the root first;
then label the entire left subtree;
then label the entire right subtree.
Given n and two node labels a and b, return the shortest path directions from node a to node b.
Directions:
U: move from the current node to its parent;
L: move from the current node to its left child;
R: move from the current node to its right child.
If a == b, output an empty string.
Input Format
n a b
Output Format
path
where path consists only of U, L, and R.
Constraints
0 <= n <= 90
1 <= a, b <= size(T(n))
size(T(0)) = size(T(1)) = 1
size(T(n)) = 1 + size(T(n-2)) + size(T(n-1))
Example 1
Input:
2 2 3
Output:
UR
Explanation: In T(2), root is 1, left child is 2, and right child is 3. From 2 to 3, go up to the root and then right.
Example 2
Input:
4 3 9
Output:
UURRR
Example
Input
2 2 3
Output
UR