从二叉树一个节点到另一个节点每一步的方向

此题解通过两次DFS搜索分别找到从根节点到起点和终点的路径。首先定义一个辅助函数path来递归地搜索树并记录路径。如果找到目标节点，函数返回True，否则返回False。在搜索过程中，遇到左子节点则路径添加'L'，遇到右子节点则路径添加'R'，如果这一分支搜索失败则将最后添加的路径字符删除。这样可以获得从根节点到任一节点的路径。在getDirections函数中，分别调用path函数获取从根节点到起点和终点的路径，然后通过比较这两个路径来确定它们的最低公共祖先。找到最低公共祖先后，计算从起点到该祖先需要多少步'U'，然后再从祖先到终点的路径。这种方法充分利用了二叉树的结构，通过路径比较来找出最短路径。

时间复杂度: O(n)

空间复杂度: O(n)

# 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 __init__(self) -> None:
        self.p=[]
    def path(self,r,d):
        # Base case: if current node is None, return False
        if not r:return False
        # Check if current node is the destination
        if r.val == d:return True
        # Traverse left child
        if r.left: 
            self.p.append('L')
            l= self.path(r.left,d)
            if l:return l
            self.p.pop()
        # Traverse right child
        if r.right: 
            self.p.append('R')
            l= self.path(r.right,d)
            if l:return l
            self.p.pop()

    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        # Get path from root to startValue
        self.path(root,startValue)
        s=''.join(self.p)
        self.p=[]
        # Get path from root to destValue
        self.path(root,destValue)
        d=''.join(self.p)
        i=j=0
        # Find lowest common ancestor
        while i<len(s) and j<len(d):
            if s[i]==d[j]:
                i+=1
                j+=1
                continue
            break
        # Compute directions: number of 'U' steps and remaining path
        return 'U'*(len(s)-i)+d[j:]