public String getDirections(TreeNode root, int startValue, int destValue) {
List<Integer> nums1 = new ArrayList<>();
List<Integer> nums2 = new ArrayList<>();
List<Character> dirs1 = new ArrayList<>();
List<Character> dirs2 = new ArrayList<>();
dfs(root, nums1, dirs1, startValue);
dfs(root, nums2, dirs2, destValue);
int k = 0;
while (k<nums1.size() && k<nums2.size() && nums1.get(k)==nums2.get(k))
k++;
for (int i=k; i<dirs1.size(); i++) dirs1.set(i,'U');
StringBuilder str = new StringBuilder();
for (Character character : dirs1.subList(k,dirs1.size())) {
str.append(character);
}
for (Character character : dirs2.subList(k,dirs2.size())) {
str.append(character);
}
return str.toString();
}
private boolean dfs(TreeNode node, List<Integer> nums, List<Character> dirs, int target) {
if (node==null) return false;
if (node.val == target) return true;
if (node.left!=null)
{
nums.add(node.left.val);
dirs.add('L');
if (dfs(node.left, nums, dirs, target))
return true;
nums.remove(nums.size()-1);
dirs.remove(dirs.size()-1);
}
if (node.right!=null)
{
nums.add(node.right.val);
dirs.add('R');
if (dfs(node.right, nums, dirs, target))
return true;
nums.remove(nums.size()-1);
dirs.remove(dirs.size()-1);
}
return false;
}