题目重点：Phone Coding 题目给两节点路径需用上左右表示；本文从根建父索引、找共同祖先、拼接向上和向下路径。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入一棵以 root 为根的二叉树、唯一整数节点值 start/destination；U 到父、L 到左孩子、R 到右孩子。
- 路径可以经过最近公共祖先；start=destination 返回空串。缺失节点或重复值报错。题目未明确这些接口与错误行为。
解题路线
- 遍历树一次，建 value→(parentValue,从父到该节点的方向)；同时检查节点值唯一。
- 从 start 向根走，记录其所有祖先；从 destination 向上直到碰到 start 的祖先，沿途收集父→子的 L/R 标签，这个交点就是 LCA。
- 从 start 向上走到 LCA，每条边输出 U；再反转 destination→LCA 途中收集的 L/R 标签，接在 U 后。
- 这避免错误地从根拼接两条完整路径；用独立的无向边带方向 BFS 对 10,000 棵随机树验证。
手动走一遍
树 1 的左孩子 2、右孩子 3；2 的右孩子 5，3 的左孩子 6。从 5 到 6：先 5→2→1 输出 UU，再 1→3→6 输出 RL，答案 UURL。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training contract: directions U/L/R between distinct nodes in a binary tree."""
from dataclasses import dataclass
@dataclass
class Node:
value: int
left: "Node | None" = None
right: "Node | None" = None
def directions(root: Node | None, start: int, destination: int) -> str:
if root is None:
raise ValueError("empty tree")
parents = {root.value: (None, "")}
stack = [root]
while stack:
node = stack.pop()
for child, edge in ((node.left, "L"), (node.right, "R")):
if child is not None:
if child.value in parents:
raise ValueError("duplicate node value")
parents[child.value] = (node.value, edge)
stack.append(child)
if start not in parents or destination not in parents:
raise ValueError("node not found")
ancestors = set()
node = start
while node is not None:
ancestors.add(node)
node = parents[node][0]
downward = []
node = destination
while node not in ancestors:
parent, edge = parents[node]
downward.append(edge)
node = parent
lca = node
upward = []
node = start
while node != lca:
upward.append("U")
node = parents[node][0]
return "".join(upward + downward[::-1])
复杂度
N 节点、树高 h：建索引 O(N) 时间/空间；两条向上链和输出 O(h) 时间/空间；整体 O(N) 时间、O(N) 空间。若需大量路径查询，可预处理 LCA 和深度，按查询量选二进制提升。
易错点与追问
容易失分的边界
- 把从 root 到 start、destination 的完整路径直接串起来，没去掉共同前缀。
- 向 destination 逆爬时收集的 L/R 没反转。
- 用节点 value 作索引却允许重复值。
- start 等于 destination 时误输出 U。
- 把题目缺约束的删除节点 rollover 高度题混写进本解法。
继续深挖
- 百万次两点路径查询，LCA 预处理怎样降低单次成本？
- 树动态插入/删除后，父索引和 LCA 结构怎样更新？
- 若节点没有唯一值，如何按对象 ID 表示输入？
- 若要最短路径长度而非方向字符串，可只计算深度与 LCA 吗？
