※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
:
: https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-
: to-another/
: 2096. Step-By-Step Directions From a Binary Tree Node to Another
: 给你一个二元树的根节点以及startValue、destValue，你可以往上、往右、往左移动，
求
: 出startValue到destValue的最短路径要怎么走。
:
思路 :
偷看到删除共同路径
就知道什么意思了
就是有点像前缀合的感觉
把走过的一样的路删掉
那些都是多余的
这样就可以找到最开始不一样的地方
那就是最短的路
我要去吃早餐了
```cpp
/**
* Definition for a binary tree node.
* 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 *left, TreeNode *right) : val(x), left(left), ri
ght(right) {}
* };
*/
class Solution {
public:
string startpath;
string destpath;
int startValuea;
string path;
void find(TreeNode* root , int target)
{
if(root == NULL)return ;
if(target == root->val)
{
if(target == startValuea)
{
startpath = path;
}
else
{
destpath = path;
}
return ;
}
path+="L";
find(root->left,target);
path.pop_back();
path+="R";
find(root->right,target);
path.pop_back();
}
string getDirections(TreeNode* root, int startValue, int destValue)
{
startValuea = startValue;
find(root,startValue);
find(root,destValue);
int sp = 0;
int dp = 0;
while(dp<destpath.size() && sp<startpath.size() && startpath[sp] == dest
path[dp])
{
sp++;
dp++;
}
string res(startpath.size()-sp,'U');
res += destpath.substr(dp,destpath.size()-dp);
return res;
}
};
```