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

这道题到底在问什么

输入

root=[50,30,80,20,40,·,·,15], start=15, dest=40

输出

"UUR"(15→20→30→40)

最优解：一步一步想明白

1. 3记住「求两条根到点路径 → 砍掉公共前缀(到 LCA)→ start 剩余转 U,接 dest 剩余」,下面逐帧套它。
2. 4start=15 dest=40先把起点 15(红)和终点 40(绿)标出来。接下来分别求「根到 15」和「根到 40」的方向串。
3. 5找 start 路径 = 空找 start:DFS 来到节点 50,还不是目标,先试着往左下走。
4. 6找 start 路径 = L先猜左边:在 50 记下 L,下探它的左孩子 30。
5. 7找 start 路径 = L找 start:DFS 来到节点 30,还不是目标,先试着往左下走。
6. 8找 start 路径 = LL先猜左边:在 30 记下 L,下探它的左孩子 20。
7. 9找 start 路径 = LL找 start:DFS 来到节点 20,还不是目标,先试着往左下走。
8. 10找 start 路径 = LLL先猜左边:在 20 记下 L,下探它的左孩子 15。
9. 11找 start 路径 = LLL走到节点 15,正是要找的 起点!
10. 12找 start = LLL根到 15 的方向串定下来:LLL(从根一路往下读)。
11. 13找 dest 路径 = 空找 dest:DFS 来到节点 50,还不是目标,先试着往左下走。
12. 14找 dest 路径 = L先猜左边:在 50 记下 L,下探它的左孩子 30。
13. 15找 dest 路径 = L找 dest:DFS 来到节点 30,还不是目标,先试着往左下走。
14. 16找 dest 路径 = LL先猜左边:在 30 记下 L,下探它的左孩子 20。
15. 17找 dest 路径 = LL找 dest:DFS 来到节点 20,还不是目标,先试着往左下走。
16. 18找 dest 路径 = LLL先猜左边:在 20 记下 L,下探它的左孩子 15。
17. 19找 dest 路径 = LLL找 dest:DFS 来到节点 15,还不是目标,先试着往左下走。
18. 20找 dest 路径 = LLLL15 没有左孩子,这个 L 走不通,马上改方向。
19. 21找 dest 路径 = LLLR15 的左子树里没有目标,回到 15、把那一步从 L 改成 R,可这边也是空的。
20. 22找 dest 路径 = LLL15 这棵子树里没有 40,把它从路径里撤掉(回溯),回到上一层换别的方向。
21. 23找 dest 路径 = LLR20 的左子树里没有目标,回到 20、把那一步从 L 改成 R,可这边也是空的。
22. 24找 dest 路径 = LL20 这棵子树里没有 40,把它从路径里撤掉(回溯),回到上一层换别的方向。
23. 25找 dest 路径 = LR30 的左子树里没有目标,回到 30、把那一步从 L 改成 R,改探右孩子 40。
24. 26找 dest 路径 = LR走到节点 40,正是要找的 终点!
25. 27找 dest = LR根到 40 的方向串定下来:LR(从根一路往下读)。
26. 28a[0]=L b[0]=L 相同逐位比 a、b:第 1 位都是 L,是公共的,顺着它走到节点 30。公共段还在往下延伸。
27. 29公共前缀长度 = 1,LCA = 30第 2 位:a 是 L、b 是 R,不一样了,公共前缀到此为止。公共段的终点节点 30 就是 start 和 dest 的最近公共祖先 LCA,从这里开始两条路就分开了。
28. 30还剩 2 步 → UUa 砍掉公共前缀后还剩 2 步(原本是往下的 LL)。现在要反过来从 15 往上爬到 LCA 30,一共 2 步,每步记一个 U,得到 UU。
29. 31下行段 = Rb 砍掉公共前缀后剩下「R」,这正是从 LCA 30 往下走到 40 的方向,照原样接在 U 段后面就行。
30. 32答案 = UUR把两段接起来:UU 加上 R,完整路线 15→…→30→…→40 的方向串就是 UUR。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
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:
        def path(n,val,p):
            if not n: return False
            if n.val==val: return True
            p.append('L')
            if path(n.left,val,p): return True
            p[-1]='R'
            if path(n.right,val,p): return True
            p.pop(); return False
        a=[]; b=[]; path(root,startValue,a); path(root,destValue,b)
        i=0
        while i<len(a) and i<len(b) and a[i]==b[i]: i+=1
        return 'U'*(len(a)-i)+''.join(b[i:])

#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: string getDirections(TreeNode* root,int startValue,int destValue){ string a,b; path(root,startValue,a); path(root,destValue,b); int i=0; while(i<a.size()&&i<b.size()&&a[i]==b[i])i++; return string(a.size()-i,'U')+b.substr(i);} bool path(TreeNode*n,int val,string& p){ if(!n)return false; if(n->val==val)return true; p.push_back('L'); if(path(n->left,val,p))return true; p.back()='R'; if(path(n->right,val,p))return true; p.pop_back(); return false;} };

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public String getDirections(TreeNode root,int startValue,int destValue){ StringBuilder a=new StringBuilder(),b=new StringBuilder(); path(root,startValue,a); path(root,destValue,b); int i=0; while(i<a.length()&&i<b.length()&&a.charAt(i)==b.charAt(i))i++; StringBuilder ans=new StringBuilder(); for(int j=i;j<a.length();j++)ans.append('U'); ans.append(b.substring(i)); return ans.toString();} boolean path(TreeNode n,int val,StringBuilder p){ if(n==null)return false; if(n.val==val)return true; p.append('L'); if(path(n.left,val,p))return true; p.setCharAt(p.length()-1,'R'); if(path(n.right,val,p))return true; p.deleteCharAt(p.length()-1); return false;} }

复杂度

面试官可能追问