_2096. Step-By-Step Directions From a Binary Tree Node to Another.md

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

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 16, 2024

Last updated : July 16, 2024

---

Related Topics : String, Tree, Depth-First Search, Binary Tree

Acceptance Rate : 56.36 %

---

Solutions

• m2096 Daily.py

Python

m2096 Daily.py

# 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:
        start, end = [], []

        def dfs(curr: Optional[TreeNode], start: List[str], target: List[str], path: List[str] = []) -> None :
            if start and target :
                return

            if curr.val == startValue :
                start.extend(path)
            if curr.val == destValue :
                target.extend(path)

            if curr.left :
                path.append('L')
                dfs(curr.left, start, target, path)
                path.pop()
            if curr.right :
                path.append('R')
                dfs(curr.right, start, target, path)
                path.pop()

        dfs(root, start, end)

        shorter = min(len(start), len(end))
        ups = 0
        while ups < shorter :
            if start[ups] != end[ups] :
                break
            ups += 1

        return 'U' * (len(start) - ups) + ''.join(end[ups:])