<p>You are given the <code>root</code> of a <strong>binary tree</strong> with <code>n</code> nodes. Each node is uniquely assigned a value from <code>1</code> to <code>n</code>. You are also given an integer <code>startValue</code> representing the value of the start node <code>s</code>, and a different integer <code>destValue</code> representing the value of the destination node <code>t</code>.</p>

<p>Find the <strong>shortest path</strong> starting from node <code>s</code> and ending at node <code>t</code>. Generate step-by-step directions of such path as a string consisting of only the <strong>uppercase</strong> letters <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;U&#39;</code>. Each letter indicates a specific direction:</p>

<ul>
	<li><code>&#39;L&#39;</code> means to go from a node to its <strong>left child</strong> node.</li>
	<li><code>&#39;R&#39;</code> means to go from a node to its <strong>right child</strong> node.</li>
	<li><code>&#39;U&#39;</code> means to go from a node to its <strong>parent</strong> node.</li>
</ul>

<p>Return <em>the step-by-step directions of the <strong>shortest path</strong> from node </em><code>s</code><em> to node</em> <code>t</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg1.png" style="width: 214px; height: 163px;" />
<pre>
<strong>Input:</strong> root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
<strong>Output:</strong> &quot;UURL&quot;
<strong>Explanation:</strong> The shortest path is: 3 &rarr; 1 &rarr; 5 &rarr; 2 &rarr; 6.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg2.png" style="width: 74px; height: 102px;" />
<pre>
<strong>Input:</strong> root = [2,1], startValue = 2, destValue = 1
<strong>Output:</strong> &quot;L&quot;
<strong>Explanation:</strong> The shortest path is: 2 &rarr; 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>All the values in the tree are <strong>unique</strong>.</li>
	<li><code>1 &lt;= startValue, destValue &lt;= n</code></li>
	<li><code>startValue != destValue</code></li>
</ul>

/**
 * 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:
    map<int,int> mp;
    map<int,TreeNode*> mper;
    void dfs(TreeNode* vertex,TreeNode* par)
    {   
        mper[vertex->val] = vertex;
        mp[vertex->val] = par->val;
        if(vertex->right) dfs(vertex->right,vertex);
        if(vertex->left) dfs(vertex->left,vertex);
    }
    bool dfs1(TreeNode* vertex,int dest, string &ans)
    {   
        if (vertex == nullptr) return false;
        if (vertex->val == dest) return true;
        ans.push_back('L');
        if (dfs1(vertex->left, dest, ans)) {
            return true;
        }
        ans.pop_back();  
        ans.push_back('R');
        if (dfs1(vertex->right, dest, ans)) {
            return true;
        }
        ans.pop_back();  
        return false;
    } 
    string getDirections(TreeNode* root, int startValue, int destValue) {
        string ans = "";
        dfs(root,root);
        map<int, bool> vis;
        int it = startValue;
        while(it != root->val) {
            vis[it] = true;
            it = mp[it];
        }
        vis[root->val] = true;
        it = destValue;
        int lca = 0;
        while(it != root->val) {
            if(vis[it])
            {
                lca = it;
                break;
            }
            it = mp[it];
        }
        if(lca==0) lca = root->val;
        cout<<lca;
        it = startValue;
        while(it!=lca)
        {
            ans+='U';
            it = mp[it];
        }
        dfs1(mper[lca],destValue,ans);
        return ans;      
    }
};
209885