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
Leave a Comment