2096. 从二叉树一个节点到另一个节点每一步的方向（Rating 1804）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1804

思路

几个点想明白，代码就写出来了

• 二叉树中，一个节点到另一个节点，一定经过二者的“最近公共祖先”节点。

• 从根节点出发，分别找开始节点和目标节点比较容易，dfs一下，向左还是向右，记录路径即可。

• 从根节点分别到开始节点和目标节点，一定有一段重复的路，即根节点 -> 二者的最近公共祖先节点这部分

那么代码就有了

• dfs下整棵树，找到并记录【根节点到开始节点的路径】和【根节点到目标节点的路径】
• 去掉相同的前缀（即根节点 -> 二者的最近公共祖先节点这部分路径），即得到最近公共祖先节点分别到开始节点和目标节点的路径
• 【最近公共祖先节点到开始节点的路径】上的‘L’和‘R’都改为‘U’
• 合并路径即为答案

代码

# 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:
        if root is None:
            return ''
        to_st, to_ed = [], [] # 分别记录到st和到ed的路径
        def dfs(node: Optional[TreeNode], path: list): # dfs
            nonlocal to_st, to_ed # 声明nolocal，不然下面的copy()赋值会把赋值对象当成局部变量
            if node.val == startValue: # 找到了开始节点，记录下路径
                to_st = path.copy()
            if node.val == destValue: # 找到了目标节点，记录下路径
                to_ed = path.copy()
            if node.left:
                path.append('L') # 准备向左节点dfs，更新路径
                dfs(node.left, path) # 向左节点dfs
                path.pop() # 回溯，dfs完要恢复原路径
            if node.right:
                path.append('R') # 准备向右节点dfs，更新路径
                dfs(node.right, path) # 向右节点dfs
                path.pop() # 回溯，dfs完要恢复原路径
        dfs(root, []) # 执行dfs
        while len(to_st) and len(to_ed) and to_st[0] == to_ed[0]: # 使用python切片特性，去除公共前缀
            to_st = to_st[1:]
            to_ed = to_ed[1:]
        return 'U' * len(to_st) + ''.join(to_ed) # 把前面的部分改为U