2024-07-16
2096. Step-By-Step Directions From a Binary Tree Node to Another
You are given the root of a binary tree with n nodes. Each node is uniquely
assigned a value from 1 to n. You are also given an integer startValue
representing the value of the start node s, and a different integer destValue
representing the value of the destination node t.
Find the shortest path starting from node s and ending at node t. Generate
step-by-step directions of such path as a string consisting of only the
uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific
direction:
'L' means to go from a node to its left child node.
'R' means to go from a node to its right child node.
'U' means to go from a node to its parent node.
Return the step-by-step directions of the shortest path from node s to node t.
分別找root 到兩個目標數的兩條path
然後把共通的點砍掉
root2src 的全部改成 U
兩條串起來就是答案
然後我想兩條一次找完 用DFS走
可能stack 操作太多了 速度有點慢
兩條分開走可能反而可以簡化一些東西
/**
* 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),
right(right) {}
* };
*/
class Solution {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
string cur_path = "";
vector<TreeNode*> nodes(1, root);
unordered_set<int> visited;
string path1;
string path2;
bool found1 = false;
bool found2 = false;
// DFS to find both path
while(!nodes.empty() && !(found1 && found2)) {
// visit
TreeNode*& cur = nodes.back();
visited.insert(cur->val);
if (!found1 && cur->val == startValue) {
found1 = true;
path1 = cur_path;
}
if (!found2 && cur->val == destValue) {
found2 = true;
path2 = cur_path;
}
// next
if (cur->left && !visited.contains(cur->left->val)) {
cur_path.push_back('L');
nodes.push_back(cur->left);
}
else if (cur->right && !visited.contains(cur->right->val)) {
cur_path.push_back('R');
nodes.push_back(cur->right);
}
else {
cur_path.pop_back();
nodes.pop_back();
}
}
//skip common path
int common = 0;
while (common < path1.size() && common < path2.size() &&
path1[common] == path2[common]) {
common++;
}
string result = string(path1.size()-common, 'U') +
path2.substr(common);
return result;
}
private:
};