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

记住「求两条根到点路径 → 砍掉公共前缀(到 LCA)→ start 剩余转 U,接 dest 剩余」,下面逐帧套它。

标出 start 与 dest：先把起点 15(红)和终点 40(绿)标出来。接下来分别求「根到 15」和「根到 40」的方向串。

找 start:到 50：找 start:DFS 来到节点 50,还不是目标,先试着往左下走。

找 start:50 试左：先猜左边:在 50 记下 L,下探它的左孩子 30。

找 start:到 30：找 start:DFS 来到节点 30,还不是目标,先试着往左下走。

找 start:30 试左：先猜左边:在 30 记下 L,下探它的左孩子 20。

找 start:到 20：找 start:DFS 来到节点 20,还不是目标,先试着往左下走。

找 start:20 试左：先猜左边:在 20 记下 L,下探它的左孩子 15。

找 start:到 15：走到节点 15,正是要找的 起点!

找 start 完成：根到 15 的方向串定下来:LLL(从根一路往下读)。

找 dest:到 50：找 dest:DFS 来到节点 50,还不是目标,先试着往左下走。

找 dest:50 试左：先猜左边:在 50 记下 L,下探它的左孩子 30。

找 dest:到 30：找 dest:DFS 来到节点 30,还不是目标,先试着往左下走。

找 dest:30 试左：先猜左边:在 30 记下 L,下探它的左孩子 20。

找 dest:到 20：找 dest:DFS 来到节点 20,还不是目标,先试着往左下走。

找 dest:20 试左：先猜左边:在 20 记下 L,下探它的左孩子 15。

找 dest:到 15：找 dest:DFS 来到节点 15,还不是目标,先试着往左下走。

找 dest:15 试左：15 没有左孩子,这个 L 走不通,马上改方向。

找 dest:15 改右：15 的左子树里没有目标,回到 15、把那一步从 L 改成 R,可这边也是空的。

找 dest:15 回退：15 这棵子树里没有 40,把它从路径里撤掉(回溯),回到上一层换别的方向。

找 dest:20 改右：20 的左子树里没有目标,回到 20、把那一步从 L 改成 R,可这边也是空的。

找 dest:20 回退：20 这棵子树里没有 40,把它从路径里撤掉(回溯),回到上一层换别的方向。

找 dest:30 改右：30 的左子树里没有目标,回到 30、把那一步从 L 改成 R,改探右孩子 40。

找 dest:到 40：走到节点 40,正是要找的 终点!

找 dest 完成：根到 40 的方向串定下来:LR(从根一路往下读)。

比第 1 位：逐位比 a、b:第 1 位都是 L,是公共的,顺着它走到节点 30。公共段还在往下延伸。

公共前缀结束 · LCA 定位：第 2 位:a 是 L、b 是 R,不一样了,公共前缀到此为止。公共段的终点节点 30 就是 start 和 dest 的最近公共祖先 LCA,从这里开始两条路就分开了。

start 剩余 → U：a 砍掉公共前缀后还剩 2 步(原本是往下的 LL)。现在要反过来从 15 往上爬到 LCA 30,一共 2 步,每步记一个 U,得到 UU。

dest 剩余 → 下行：b 砍掉公共前缀后剩下「R」,这正是从 LCA 30 往下走到 40 的方向,照原样接在 U 段后面就行。

答案 = U段 + 下行段：把两段接起来:UU 加上 R,完整路线 15→…→30→…→40 的方向串就是 UUR。

边界:祖先关系时只有 U 或只有下行;分居两侧则 LCA 是根。

两个追问:可先求 LCA 再算;路径串长 O(h)、不会爆。