2096. Step-By-Step Directions From a Binary Tree Node to Another

use 2 StringBuilder

T: O(n)

S: O(n)

class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder dir1 = new StringBuilder();
        StringBuilder dir2 = new StringBuilder();

        dfs(root, startValue, dir1);
        dfs(root, destValue, dir2);
        
        int len1 = dir1.length();
        int len2 = dir2.length();
        int same = 0;
        
        // 如果要去 commons, 要從後面看過來, 因為 string builder 是 append
        
        while (len1 - same - 1 >= 0 && len2 - same - 1 >= 0 && 
               dir1.charAt(len1 - same - 1) == dir2.charAt(len2 - same - 1)) {
            same++;
        }
        for (int i = same; i < len1;i++) {
            dir1.setCharAt(i, 'U');
        }
        
        // 要 reverse, 因為 string builder 是 append
        return dir1.substring(same, len1) + dir2.reverse().substring(same, len2);
    }
    private boolean dfs(TreeNode root, int target, StringBuilder sb) {
        if (root == null) {
            return false;
        }
        if (root.val == target) {
            return true;
        }
        if (root.left != null) {
            // 因為先下探, ok, 才會加, 所以是倒著加回來的
            if (dfs(root.left, target, sb)) {
                sb.append("L");
                return true;
            }
        }
        if (root.right != null) {
            if (dfs(root.right, target, sb)) {
                sb.append("R");
                return true;
            }
        }
        return false;
    }
}

easy to understand one

class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder dir1 = new StringBuilder();
        StringBuilder dir2 = new StringBuilder();
        
        dfs(root, startValue, dir1);
        dfs(root, destValue, dir2);

        // our tree dfs is going to deep, then start to append
        // so [5,1,2,3,null,6,4] this case, 
        // 3 -> 1 -> 5 will goes to 3 then sb append L, then 1, append L, dir1 = LL
        // 5 -> 2 -> 6, will goes to 6 append L, then 2, append R, dir2 = LR
        // so we reverse the string, easy to compare the common LCA part
        String d1 = dir1.reverse().toString(); // LL
        String d2 = dir2.reverse().toString(); // RL
        
        // so in here, same = 0, LL from index 0, not same as RL index 0
        int same = 0;
        while (same < d1.length() && same < d2.length() && d1.charAt(same) == d2.charAt(same)) {
            same++;
        }

        // so in the last, just reapt "U" + d2 string(remove same part)(has reversed!)
        return "U".repeat(d1.length() - same) + d2.substring(same);
    }
    private boolean dfs(TreeNode root, int target, StringBuilder sb) {
        if (root == null) {
            return false;
        }
        if (root.val == target) {
            return true;
        }
        if (root.left != null) {
             // if has root left and true, then append L
            if (dfs(root.left, target, sb)) {
                sb.append("L");
                return true;
            }
        }
        if (root.right != null) {
            if (dfs(root.right, target, sb)) {
                sb.append("R");
                return true;
            }
        }
        return false;
    }
}