1
class Solution {
2

3
  private boolean DFS(TreeNode currNode, StringBuilder path, int destVal) {
4
    if (currNode == null) return false;
5
    if (currNode.val == destVal) return true;
6
    if (DFS(currNode.left, path, destVal)) path.append("L");
7
    else if (DFS(currNode.right, path, destVal)) path.append("R");
8
    return path.length() > 0;
9
  }
10

11
  public String getDirections(TreeNode root, int startValue, int destValue) {
12
    StringBuilder startToRoot = new StringBuilder();
13
    StringBuilder endToRoot = new StringBuilder();
14

15
    DFS(root, startToRoot, startValue);
16
    DFS(root, endToRoot, destValue);
17

18
    int i = startToRoot.length(), j = endToRoot.length();
19
    int cnt = 0;
20
    while (i > 0 && j > 0 && startToRoot.charAt(i - 1) == endToRoot.charAt(j - 1)) {
21
      cnt++;
22
      i--;
23
      j--;
24
    }
25

26
    String sPath = "U".repeat(startToRoot.length() - cnt);
27
    String ePath = endToRoot.reverse().toString().substring(cnt, endToRoot.length());
28

29
    return sPath + ePath;
30
  }
31
}