You are given the
root of a binary tree with
n nodes. Each node is uniquely assigned a value from
n. You are also given an integer
startValue representing the value of the start node
s, and a different integer
destValue representing the value of the destination node
Find the shortest path starting from node
s and ending at node
t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters
'U'. Each letter indicates a specific direction:
'L'means to go from a node to its left child node.
'R'means to go from a node to its right child node.
'U'means to go from a node to its parent node.
Return the step-by-step directions of the shortest path from node
s to node
5 / \ 1 2 / / \ 3 6 4 Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6 Output: "UURL" Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.
2 / 1 Input: root = [2,1], startValue = 2, destValue = 1 Output: "L" Explanation: The shortest path is: 2 → 1.
- The number of nodes in the tree is
2 <= n <= 105
1 <= Node.val <= n
- All the values in the tree are unique.
1 <= startValue, destValue <= n
startValue != destValue
Traverse the tree to find the paths from root to the two nodes, remove the common prefix, and change the path to the left node (the one found first) to all "up(U)".