LeetCode2096 从二叉树一个节点到另一个节点每一步的方向
最近公共祖先的变形题.
# 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:
father, s, t = {}, None, None
def dfs(cur: TreeNode) -> None:
nonlocal s, t
if cur.val == startValue: s = cur
if cur.val == destValue: t = cur
if cur.left:
father[cur.left] = cur
dfs(cur.left)
if cur.right:
father[cur.right] = cur
dfs(cur.right)
dfs(root)
def get_path(cur: TreeNode) -> List[str]:
ret = []
while cur != root:
parent = father[cur]
if cur == parent.left: ret.append('L')
elif cur == parent.right: ret.append('R')
cur = parent
return ret[::-1]
s_path, t_path = get_path(s), get_path(t)
while s_path and t_path and s_path[0] == t_path[0]:
s_path.pop(0), t_path.pop(0)
ans = 'U' * len(s_path) + ''.join(t_path)
return ans