<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.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getInstrsToStartAndDest(self, root, start_value, dest_value, cur_path=None):
        start_path = None
        dest_path = None

        if cur_path is None:
            cur_path = []

        if root.val == start_value:
            start_path = cur_path + ["S"]
        elif root.val == dest_value:
            dest_path = cur_path + ["S"]

        if root.left or root.right:
            if root.left:
                new_path = cur_path + [("L", root.val)]

                left_start, left_dest = self.getInstrsToStartAndDest(root.left, start_value, dest_value, new_path)
                if left_start:
                    start_path = left_start
                if left_dest:
                    dest_path = left_dest
            if root.right:
                new_path = cur_path + [("R", root.val)]

                right_start, right_dest = self.getInstrsToStartAndDest(root.right, start_value, dest_value, new_path)
                if right_start:
                    start_path = right_start
                if right_dest:
                    dest_path = right_dest

        return start_path, dest_path

    # def print_tree(self, root, prefix):
    #     my_str = prefix + str(root.val)
    #     if root.left:
    #         my_str += f"\n{prefix}|" + self.print_tree(root.left, prefix + " ")
    #     if root.right:
    #         my_str += f"\n{prefix}|" + self.print_tree(root.right, prefix + " ")
    #     return my_str

    def getClosestParent(self, root, start_value, dest_value):
        seen_start = False
        seen_dest = False
        if root.left or root.right:
            if root.left:
                left_closest, left_seen_start, left_seen_dest = self.getClosestParent(
                    root.left, start_value, dest_value
                )
                if left_seen_start and left_seen_dest:
                    return left_closest, True, True

                seen_start = max(seen_start, left_seen_start)
                seen_dest = max(seen_dest, left_seen_dest)
            if root.right:
                right_closest, right_seen_start, right_seen_dest = self.getClosestParent(
                    root.right, start_value, dest_value
                )
                if right_seen_start and right_seen_dest:
                    return right_closest, True, True
                seen_start = max(seen_start, right_seen_start)
                seen_dest = max(seen_dest, right_seen_dest)

        if root.val == start_value:
            seen_start = True
        elif root.val == dest_value:
            seen_dest = True

        return root, seen_start, seen_dest


    def getInstrsTo(self, root, value):
        if root.val == value:
            return "S"
        elif root.left or root.right:
            if root.left:
                left_path = self.getInstrsTo(root.left, value)
                if left_path:
                    return "L" + left_path
            if root.right:
                right_path = self.getInstrsTo(root.right, value)
                if right_path:
                    return "R" + right_path
        return None

    def getAllInstrsTo(self, root, start_value, dest_value):
        start_path = ""
        dest_path = ""
        if root.val == start_value:
            start_path = "S"
        if root.val == dest_value:
            dest_path = "S"

        if root.left or root.right:
            if root.left:
                left_start_path, left_dest_path = self.getInstrsTo(root.left, start_value, dest_value)
                if left_start_path and left_start_path[-1] == "S":
                    start_path = "L" + left_start_path
                if left_dest_path and left_dest_path[-1] == "S":
                    dest_path = "L" + left_dest_path
            if root.right:
                right_start_path, right_dest_path = self.getInstrsTo(root.right, start_value, dest_value)
                if right_start_path and right_start_path[-1] == "S":
                    start_path = "R" + right_start_path
                if right_dest_path and right_dest_path[-1] == "S":
                    dest_path = "R" + right_dest_path
        return start_path, dest_path

    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        if root is None:
            return ""

        closest_parent, _, _ = self.getClosestParent(root, startValue, destValue)
        start_instrs = self.getInstrsTo(closest_parent, startValue)
        dest_instrs = self.getInstrsTo(closest_parent, destValue)

        # start_instrs, dest_instrs = self.getAllInstrsTo(closest_parent, startValue, destValue)
        instrs = "".join(["U" for _ in range(len(start_instrs) - 1)])
        # instrs += dest_instrs[:-1]
        # return "".join(instrs)
        return instrs + dest_instrs[:-1]
        
58643