#2096

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

specialist · 770 · lc medium +31 · verified · 56.4% accepted · 3,250 likes · top 51%

Description

You are given the root of a binary tree with n nodes. Each node has a unique value from 1 to 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 t.

Determine the shortest path from node s to node t and encode it as a string using only the uppercase letters 'L', 'R', and 'U', where each character represents a movement:

- 'L' means move to the left child.

- 'R' means move to the right child.

- 'U' means move to the parent.

Return the encoded string describing the shortest path from s to t.

Example 1:

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.

Example 2:

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

Output: "L"

Explanation: The shortest path is: 2 → 1.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str: