Leetcode 2217 Solution

This article provides solution to leetcode question 2217 (step-by-step-directions-from-a-binary-tree-node-to-another)
Categories:
Tags:
Access this page by simply typing in "lcs 2217" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another

Solution

# 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:
        def findpath(node, value, path):
            if not node:
                return False

            if node.val == value:
                return True

            if findpath(node.left, value, path):
                path.append('L')
                return True

            if findpath(node.right, value, path):
                path.append('R')
                return True

            return False

        start_path = []
        findpath(root, startValue, start_path)

        end_path = []
        findpath(root, destValue, end_path)

        i = len(start_path) - 1
        j = len(end_path) - 1

        while i >= 0 and j >= 0 and start_path[i] == end_path[j]:
            i -= 1
            j -= 1

        ans = 'U' * (i + 1)
        while j >= 0:
            ans += end_path[j]
            j -= 1

        return ans