# Untitled

unknown
python
17 days ago
1.9 kB
3
Indexable
Never
```# 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:
# Use DFS to find the path from root to target
def dfs(node: Optional[TreeNode], target: int, path: List[str]) -> bool:
if not node:
return False

if node.val == target:
return True

# We first check if we found the target and then append the path
# This means we only accumulate the path when stackframes are popping/returning
# This causes the path to be reversed (target-to-root)
if dfs(node.left, target, path):
path += "L"
elif dfs(node.right, target, path):
path += "R"

return len(path) > 0

startPath, destPath = [], []
dfs(root, startValue, startPath)
dfs(root, destValue, destPath)

# We now have target-to-root paths from each of start and destination
# That means movements from root are at the end of the path
# We can remove redundant movements
# This is effectively pruning common ancestors until we find the lowest
while len(startPath) > 0 and len(destPath) > 0 and startPath[-1] == destPath[-1]:
startPath.pop()
destPath.pop()

# Now, we join together the two paths
# Every movement in the start path is just an 'up' direction
# We keep the movements in the destination path (reversing for root-to-target)
up = "".join("U" * len(startPath))
down = "".join(reversed(destPath))
return up + down
```