문제

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• 처음에는 각 depth마다 가장 오른쪽 노드가 있는지 구하는 문제인줄 알아서 현재 node의 오른쪽 자식이 있는지만 체크하며 return 해주었지만 틀림 => depth마다 가장 오른쪽에 있는 노드를 출력하는 문제였음
• root 노드에서 시작해 노드를 순회할 때, 오른쪽 자식이 있는지 먼저 체크하고 없다면, 왼쪽 노드를 체크하는 방식으로 전체 트리를 순회하면서 각 depth 별로 처음 만나는 노드를 저장하여 return 하는 방식으로 해결
• 먼저 나오는 순서대로 List에 넣어준다면 아래와 같은 경우 [3, 5, 1]로 구해지고, HashMap을 사용한다면 Key를 기준으로 정렬하는 과정이 더 필요하기 때문에 배열을 사용하여 배열[i] = i번째 depth에서 가장 먼저 만난 노드 = i 번째 depth에서 가장 우측에 있는 노드로 먼저 답을 구하고, List형으로 변환하여 return 함으로써 문제를 해결할 수 있었음

코드

class Solution {
    int[] rightArray;

    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        rightArray = new int[101];
        Arrays.fill(rightArray, Integer.MIN_VALUE);
        check(root, 1);

        List<Integer> answer = new ArrayList<>();
        for (int i = 1 ; i <= 100 ; i ++) {
            if (rightArray[i] == Integer.MIN_VALUE) break;
            answer.add(rightArray[i]);
        }

        return answer;
    }

    private void check(TreeNode now, int depth) {
        if (rightArray[depth] == Integer.MIN_VALUE) {
            rightArray[depth] = now.val;
        }

        if (now.right != null) check(now.right, depth+1);
        if (now.left != null) check(now.left, depth + 1);
    }
}

결과