Re: [閒聊] 每日leetcode已回收
※ 引述 《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;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.33.183 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721105213.A.CC3.html
推
07/16 12:50,
1年前
, 1F
07/16 12:50, 1F
推
07/16 12:51,
1年前
, 2F
07/16 12:51, 2F
推
07/16 12:54,
1年前
, 3F
07/16 12:54, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 506 之 1548 篇)：