# 2096. Step-By-Step Directions From a Binary Tree Node to Another
###### tags: `Leetcode` `Medium` `Tree` `LCA`
Link: https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
## 思路
思路参考[这里](https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/discuss/1612105/3-Steps)
1. 先找到从root到value点的路径怎么走
Say we get "LLRRL" and "LRR".
2. 把两个字符串反转过来(才是真正从root到目标点的路径) 找到commonpath 因为那是到start和dest都要走的路径
We remove "L", and now start direction is "LRRL", and destination - "RR"
3. Replace all steps in the start direction to "U" and add destination direction.
The result is "UUUU" + "RR".

没有直接用lca模版的原因是它需要知道从root到每个node的路径 也就是他需要从上至下的信息 而不是从下至上的
但是找lca的过程是从下至上的 (下面的child node告诉你它的subtree有没有target node)
直接用lca会比较麻烦
## Code

class Solution {
    //other solutions
    private boolean findNode(TreeNode root, int value, StringBuilder sb){
        if(root.val==value) return true;
        if(root.left!=null && findNode(root.left, value, sb)){
            sb.append('L');
            return true;
        }
        else if(root.right!=null && findNode(root.right, value, sb)){
            sb.append('R');
            return true;
        }
        return false;
    }
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder start = new StringBuilder();
        StringBuilder dest = new StringBuilder();
        findNode(root, startValue, start);
        findNode(root, destValue, dest);
        start = start.reverse();
        dest = dest.reverse();
        int commonIdx = -1;
        for(int i=0; i<Math.min(start.length(), dest.length()); i++){
            if(start.charAt(i)==dest.charAt(i)) commonIdx = i;
            else break;
        }
        return "U".repeat(start.length()-commonIdx-1)+dest.substring(commonIdx+1);
    }
}