Step-By-Step Directions From a Binary Tree Node to Another

A binary tree contains n nodes with distinct values from 1 to n. Given the tree root and two different node values, startValue and destValue, return the directions for the shortest path from the start node to the destination.

Use L to move to a left child, R to move to a right child, and U to move to a parent. Concatenate these letters in the order of the moves.

Examples represent the tree in level order, with null for missing children and trailing nulls omitted.

Example 1:

Input: root = [1,2,3,4,5,6,7]
startValue = 4
destValue = 7

Output: "UURR"

Explanation: Move from 4 up to 2, then up to 1, right to 3, and right to 7. The direction string is UURR.

Example 2:

Input: root = [2,1,3]
startValue = 2
destValue = 3

Output: "R"

Explanation: The destination 3 is the right child of the starting node 2, so one rightward move is enough.

Example 3:

Input: root = [1,null,2,3]
startValue = 3
destValue = 1

Output: "UU"

Explanation: Node 3 has parent 2, whose parent is 1. Two upward moves reach the destination.

Constraints:

• The tree contains n nodes, where 2 <= n <= 10^5.
• The node values are distinct integers from 1 to n.
• 1 <= startValue, destValue <= n
• startValue != destValue