[코테연습] 2096. Step-By-Step Directions From a Binary Tree Node to Another

- TreeNode

 

class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder startStr = new StringBuilder();
        find(root, startValue, startStr);
        StringBuilder destStr = new StringBuilder();
        find(root, destValue, destStr);

        // 끝에서 경로를 비교하여 공통 경로 길이를 찾습니다.
        int index = 0;
        int maxLength = Math.min(startStr.length(), destStr.length());
        while(index < maxLength && startStr.charAt(startStr.length() - index - 1) == destStr.charAt(destStr.length() -index -1)) {
            ++index;
        } 
        // 결과는 일련의 'U' 문자(시작 노드에서 공통 조상으로 이동)입니다
        // 그리고 나머지 경로를 따라 목적지 노드로 이동합니다.
        return "U".repeat(startStr.length() - index) + destStr.reverse().toString().substring(index);
    }
    // 루트에서 주어진 노드까지의 경로를 값 'val'로 찾는 도우미 기능.
    // 왼쪽으로 가면 'L'이, 오른쪽으로 가면 'R'이 붙습니다.
    boolean find(TreeNode root, int val, StringBuilder direct) {
        // 현재 노드의 값이 목표 값과 일치하면 true를 반환합니다.
        if (root.val == val) {
            return true;
        }
        // 목표값이 왼쪽 부분 트리에 있는지 확인합니다.
        if (root.left != null && find(root.left, val, direct)) {
            direct.append("L");
        // 목표값이 오른쪽 부분 트리에 있는지 확인합니다.
        } else if (root.right != null && find(root.right, val, direct)) {
            direct.append("R");
        }
        // 경로(왼쪽 또는 오른쪽)가 발견되면 true로 반환합니다.
        return direct.length() > 0;
    }

}