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.
Solution
和 Oracle 有道题很像，那道题是求出最短路径的长度，这里让我们输出路径。
第一步依然是求出 \(LCA\). 很显然从 \(s\) 出发到 \(LCA\) 的路径必然是 \(U...\)，从 \(LCA\) 到 \(t\) 则是正常的 \(dfs\) 顺序即可。这里用 \(dfs\) 函数来判断当前的 \(v\) 是否存在 \(rt\) 为根的树里面。我们先将 \(L\) 加入到路径当中，如果不在该左子树里面，则 \(pop\_back\) 即可。
点击查看代码
/**
* 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 {
private:
string lca_to_p = "";
string lca_to_q = "";
TreeNode* LCA(TreeNode* rt, int p, int q){
if(!rt) return NULL;
if(rt->val==p || rt->val==q) return rt;
TreeNode* lrt = LCA(rt->left, p, q);
TreeNode* rrt = LCA(rt->right, p, q);
if(lrt && rrt) return rt;
else if(!lrt && !rrt) return NULL;
return lrt?lrt:rrt;
}
bool dfs(TreeNode* rt, string& res, int v){
if(!rt) return false;
if(rt->val == v) return true;
res.push_back('L');
if(dfs(rt->left, res, v)){
return true;
}
res.pop_back();
res.push_back('R');
if(dfs(rt->right, res, v)){
return true;
}
res.pop_back();
return false;
}
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
TreeNode* lca = LCA(root, startValue, destValue);
dfs(lca, lca_to_p, startValue);
dfs(lca, lca_to_q, destValue);
for(auto &ele: lca_to_p){
ele = 'U';
}
return lca_to_p+lca_to_q;
}
};